Մրցանակներ
Ալիսան և Բոբը հաղթել են հեռուստատեսային վիկտորինայում, և պետք է մրցանակներ ստանան։ Նրանք պետք է
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^9Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB