SPOJ in Armenian

Ալիսան և Բոբը հաղթել են հեռուստատեսային վիկտորինայում, և պետք է մրցանակներ ստանան։ Նրանք պետք է n մրցանակներից, որոնք համարակալված են 1-ից n թվերով, ընտրություն անեն։

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

Ալիսան լավ գիտի Բոբին, և յուրաքանչյուր մրցանակի համար պարզել է, թե որքան է այն արժեքավոր Բոբի համար։ Այդ արժեքներ ամբողջ թվեր են։ Ալիսան նեղացած է Բոբից և ցանկանում է իր մրցանակներն ընտրել այնպես, որ Բոբի ընտրած մրցանակների արժեքների գումարը որքան հնարավոր է փոքր լինի։ Ընդ որում, Ալիսային չի հետաքրքրում, թե իրեն ինչ մրցանակներ բաժին կհասնեն։

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

Մուտք

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

Ելք

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

Օրինակ.

Մուտք.
10 2

1 2 4 5 2 4 2 2 1 6

ելք.
7

Պարզաբանում

Ալիսան կարող է ընտրել 4-րդ և 5-րդ մրցանակները, որից հետո Բոբի համար լավագույնը կլինի ընտրել 9-րդ և 10-րդ մրցանակները։