E. Шаазан эдлэл

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

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

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

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

Уурлаж бухимдсан үеэдээ гүнж цууглуулгийн шаазан эдлэлээсээ хэдийг хагалдаг. Маш их уурлаж бухимдах бүртээ тэрээр ямар нэг зүйл хагалж таарна.

Шаазан эдлэлийн цуглуулгыг $n$ тавиурууд дээр цэгцтэй эгнүүлэн өржээ. Тавиур бүрт шаазан эдлэлүүдийг нэг эгнээ болгон өрсөн байх учир тавиурны голын шаазан эдлэлт хүрэх боломжгүй харин хамгийн захад, баруун талд, зүүн талд өрсөн эдлүүдэд л хүрэх боломжтой байв. Эгнээнээс нэг шаазан эдлэл авч чадвал түүний хажуугийнхыг ч мөн авах боломжтой болно гэсэн үг (жишээ харна уу). Эгнээнээс нэг эдлэл авсан бол буцааж тавьж болохгүй.

Танд бүх шаазан эдлэлийн үнэ өгөгджээ. Таны даалгавар бол $m$ удаа ууралсан үедээ гүнж өөрийн шаазан цуглуулгатаа учруулж болох хамгийн их хохирлыг олох явдал юм.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 100$) болон $m$ ($1 ≤ m ≤ 10000$) гэсэн хоёр бүхэл тоо агуулна. Дараагийн мөр нь тавиур дээр байх шаазан эдлэлүүдийн үнийг агуулна: эхний тоо нь тавиур дээр байх шаазан эдлэлүүдийн тоог харуулах бол ($1$-ээс $100$ хоёрын хооронд), дараагийн тоо нь эдлэлүүдийн үнийг харуулна. Эдгээрийг тавиур дээр өрөгдсөн дарааллаараа ийхнүү дугаарлагджээ (эхний тоо нь хамгийн зүүн талд байгаа эдлэлийг илтгэх бол хамгийн сүүлийн тоо хамгийн сүүлийн шаазан эдлэлийг харуулна). Хамгийн багадаа нийт $m$ тооны шаазан эдлэл байна гэж үзнэ.

Гаралт

Гаралтд $m$ удаа уурлаж хилэгнэх үед учирч болох хамгийн их хохирлыг олоорой.

Орчуулсан: Энхгэрэл

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

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

Тэмдэглэл

Эхний жишээнд тус бүр 3 эдлэл агуулсан хоёр тавиур байна. Сонгосон эдлэлийн нийт өртгийг өсгөхийн тулд та эхний тавиурын зүүн талаас хоёр шаазан эдлэл, хоёр дахь тавиурын баруун талаас нэгийг авч болно. Хоёр дахь жишээнд зөвхөн нэг тавиур байна. Тиймээс түүн дээр байгаа 3 шаазан эдлэлийг бүгдийг нь авна- хоёрыг зүүн талаас, нэгийг баруун талаас.

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