Մրցանակներ

Ալիսան և Բոբը հաղթել են հեռուստատեսային վիկտորինայում, և պետք է մրցանակներ ստանան։ Նրանք պետք է n մրցանակներից, որոնք համարակալված են 1-ից n թվերով, ընտրություն անեն։ Մրցանակների բաշխումը նախատեսված է անցկացնել հետևյալ կերպ: Վիկտորինայի կազմակերպիչները հաղթողներին ասում են մի k (1 ≤ k ≤ n / 3) թիվ։ Սկզբում Ալիսան ընտրում է իր համար իրար հաջորդող k մրցանակների համարներ։ Հետո Բոբն է ընտրում իրար հաջորդող k մրցանակների համարներ, Ալիսայի ընտրածից տարբեր։ Հետո հաղթողները վերցնում են իրենց մրցանակները։ Ալիսան լավ գիտի Բոբին, և յուրաքանչյուր մրցանակի համար պարզել է, թե որքան է այն արժեքավոր Բոբի համար։ Այդ արժեքներն ամբողջ թվեր են։ Ալիսան նեղացած է Բոբից և ցանկանում է իր մրցանակներն ընտրել այնպես, որ Բոբի ընտրած մրցանակների արժեքների գումարը որքան հնարավոր է փոքր լինի։ Ընդ որում, Ալիսային չի հետաքրքրում, թե իրեն ինչ մրցանակներ բաժին կհասնեն։ Պահանջվում է գրել ծրագիր, որը գտնի այն մինիմալ x թիվը, որից ավել արժողությամբ մրցանակ Բոբը չի կարող ստանալ, եթե Ալիսան լավագույն քայլ կատարի։

Մուտքային տվյալներ

Առաջին տողում տրված են մրցանակների n քանակը և k թիվը (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3)։ Երկրորդ տողում տրված են n ամբողջ թվեր՝ մրցանակների ai արժեքները (1 ≤ ai ≤ 109):

Ելքային տվյալներ

Պետք է արտածել այն մինիմալ x թիվը, որին կարող է հասնել Ալիսան այնպես, որ Բոբը չկարողանա x-ից ավել գումարային արժեքով մրցանակներ վերցնել։

Օրինակ

Մուտք
Ելք
10 2 1 2 4 5 2 4 2 2 1 6
7
Պարզաբանում. Ալիսան կարող է ընտրել 4-րդ և 5-րդ մրցանակները, որից հետո Բոբի համար լավագույնը կլինի ընտրել 9-րդ և 10-րդ մրցանակները։ Ենթախնդիր 1 (30 միավոր) 3 ≤ n ≤ 50, 1 ≤ ai ≤ 10^5  Ենթախնդիր 2 (30 միավոր) 3 ≤ n ≤ 5000, 1 ≤ ai ≤ 10^5  Ենթախնդիր 3 (40 միավոր) 3 ≤ n ≤ 100 000, 1 ≤ ai ≤ 10^9

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue