B. Дима ба ажлын жагсаалт

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Та Дима сайхан амрахад тусалсан бол одоо ажиллах цаг болсон. Найз охинтой бусад эрчүүдийн адил Дима төрлөхийн бүх зүйлийг буруу хийдэг.

Ина, Дима хоёр одоо нэг өрөөнд байгаа. Ина, Димад хэлэхдээ түүний дэргэд байхдаа хийж байгаа бүх зүйлээ боль гэжээ. Ина түүнд зарим зүйлийг боль гэж хэлсний дараа өөр өрөөрүү орж тэндээ түүний хайрт ямар хойрго болохыг үглэн тойрон алхдаг. Тэр хугацаанд Дима $k - 1$ ажлыг тайван гүйцэтгэх хугацаатай болдог. Тэгээд Ина, Дима дээр буцаж ирэн түүний дэргэд хийх дараагийн ажлаа болихийг хэлэн өөр өрөөрүү дахиад ордог. Энэ үйл явц Дима бүх ажлаа хийж дуусан хүртэл явагддаг.

Нийтдээ Димад 1-ээс $n$ хүртэл дугаарлагдсан хийх $n$ ажил байгаа. Дима эрбэ дараалалд дуртай бөгөөд ямар нэг ажлаас эхлэн ажлуудыг дараалан гүйцэтгэдэг. Жишээ нь Димад хийх нийт 6 ажил байгаа ба хэрэв тэр 5-р ажлаас эхэлсэн бол хийх дараалал нь: эхлээд Дима 5-р ажлыг, дараагаар 6-р ажлыг, дараагаар 1-р ажлыг, дараагаар 2-р ажлыг, дараагаар 3-р ажлыг, тэгээд 4-р ажлыг.

Ина, Димад ситемтэйгээр, маш олон удаа болихыг хэлдэг (зөвхөн найрсагаар, тохиромжтойгоор) ба Дима ажил бүрийг нь зогсоох түүний ятгалтын хүчийг мэднэ. Димад аль болох багаар боль гэж хэлүүлэхэд сонгох ёстой хамгийн эхний ажлыг олоход тусал.

Оролт

Эхний мөр $n, k (1 <= k <= n <= 10^5)$ хоёр бүхэл тоог агуулна. Дараагийн мөр $a_1, a_2, ..., a_n (1 <= a_i <= 10^3)$ гэсэн $n$ бүхэл тоог агуулах ба $a_i$ нь Ина, Димад $i$ дахь ажлыг хийж байхад болихыг хэлж байгаа хүч.

$n$ нь үргэлж $k$-д хуваагдах нь баталгаатай.

Гаралт

Хамгийн багаар боль гэж хэлүүлэхэд Димагийн эхлэн хийх ажлын тоог нэг мөрөнд гаргана. Хэрэв олон хариу байгаа бол, хамгийн бага дугаартай ажлыг хэвлэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
6 2
3 2 1 6 5 4
Гаралт
1
Оролт
10 5
1 3 5 7 9 9 4 1 8 5
Гаралт
3

Тэмдэглэл

Эхний жишээний тайлбар.

Хэрэв Дима эхний ажлаас эхэлвэл, Ина түүнд 3 хүчээр боль гэж хэлнэ тэгвэл Дима ахиад (k = 2 тул) нэг ажлыг хийж чадна, дараагаар нь Ина 3 дахь ажлыг болихыг 1 хүчтэйгээр хэлнэ, тэгээд тэр тав дахь алыг болихыг 5 хүчтэйгээр хэлнэ. Тиймээс Дима нийт $3 + 1 + 5 = 9$ хүчээр хэлүүлсэн байна. Хэрэв жишээ нь Димай хоёр дахь ажлаас эхэлвэл Ина түүнд $2, 4, 6$ дугаар ажлыг болихыг $2 + 6 + 4 = 12$ хүчээр хэлнэ.

Хоёр дугаар жишээний тайлбар

Хоёр дахь жишээнд k = 5 тиймээс Дима түүний хэлэх завсар 4 ажлыг хийж дуусгаж чадна. Тэгэхээр Ина Ина, Димад 1, 6-р ажлыг болихыг хэлнэ (хэрэв тэр 1 эсвэл 6-аас эхэлсэн бол), 2, 7-р ажлыг (хэрэв тэр 2, 7-р ажлаас эхэлсэн бол) г.м. Хамгийн тохиромжтой хариул нь 3 эсвэл 8-р ажлыг эхлэн хийх бөгөөд 3 бага дугаартай учраас 3 хариу юм.

Сэтгэгдлүүдийг ачааллаж байна...