B. Илүү үхрийн хонх

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

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

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

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

Кевин Сан өөрийн $n$ ширхэг үхрийн хонх бүхий үнэт цуглуулгыг Напертриллээс үнэндээ үр тариагүй өвстэй Ексетэррүү зөөхийг хүсч байна. Зөөхийн өмнө тогтмол хэмжээтэй $k$ хайрцаганд үхрийн хонхнуудаа савлах ёстой. Тээвэрлэлтийн үед цуглуулгаа аюулгүй байлгахын тулд тэр нэг хайрцаганд хоёроос их үхрийн хонх байрлуулахыг хүсэхгүй. Кевин зардалыг багасгахыг хүсч байгаагаас хойш өөрийн цуглуулгыг бүхэлд нь савлаж чадах хамгийн бага хэмжээтэй хайрцгийг сонирхож байна.

Кевин нямбай үхрийн хонх цуглуулагч ба түүний $i$-р ($1 ≤ i ≤ n$) үхрийн хонхны хэмжээ нь бүхэл тоон утга $s_{i}$ гэдгийг мэднэ. Үнэндээ түүний үхрийн хонхнууд хэмжээгээрээ эрэмбэлэгдсэн ба дурын $i > 1$ хувьд $s_{i - 1} ≤ s_{i}$ байна. Хэрвээ нэг эсвэл хоёр үхрийн хонхнуудын хэмжээнүүдийн нийлбэр хайрцагны хэмжээ $s$-c хэтрэхгүй байвал мэргэжлийн савлагч Кевин уг үхрийн хонхнуудыг $s$ хэмжээтэй хайрцаганд тааруулж чадна. Мэдээлэл өгөгдсөн бол Кевинд $s$ хэмжээтэй $k$ ширхэг хайрцаганд бүх үхрийн хонхнуудаа багтааж чадах боломжит хамгийн бага $s$-г тодорхойлоход туслана уу.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 2*k ≤ 100 000$) байх ба харгалзан үхрийн хонхнуудын тоо болон хайрцагуудын тоо байна.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $s_{1}, s_{2}, ..., s_{n}$ ($1 ≤ s_{1} ≤ s_{2} ≤ ... ≤ s_{n} ≤ 1 000 000$) байх ба Кевиний үхрийн хонхнуудын хэмжээ байна. $s_{i}$ хэмжээнүүд нь өсөх дарааллаар өгөгдөнө.

Гаралт

Кевин $s$ хэмжээтэй $k$ ширхэг хайрцаганд бүх үхрийн хонхнуудаа багтааж чадах боломжит хамгийн бага $s$-г илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Эхний жишээн дээр Кевин өөрийн хоёр үхрийн хонхоо нэг хайрцаганд хийх ёстой.

Хоёр дахь жишээн дээр Кевин дараах үхрийн хонхнуудын бүрдлүүдийг савлах ёстой: ${2, 3}$ ба ${5}$ болон ${9}$.

Гурав дахь жишээн дээр хамгийн тохиромжтой шийдэл бол ${3, 5}$ ба ${7}$ юм.

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