B. Design Tutorial: Бодит явдлаас сэдэвлэх

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

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

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

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

Шинэ бодлого зохиох бас боломжит нэг арга бол бодит явдлаас сэдэвлэх юм. Та бодитоор тохиолддог ямар нэг явдлыг сонгоод, үүнийгээ загварчлан шинэ бодлого зохиож болно. Жишээ нь, олон хүн цахилгаан шат хүлээн зогсож байгаа бөгөөд хүн бүр тодорхой давхрууд руу явахыг хүсэж байгаа. Бид дараах байдлаар загварчилъя.

Бидэнд нэг давхарт зогсож байгаа $n$ хүн байгаа ба $i$-р хүн $f_{i}$ давхар луу явахыг хүсэж байгаа. Харамсалтай нь ганцхан л цахилгаан шат байгаа бөгөөд энэ нь $k$ (хамгийн ихдээ нэгэн зэрэг $k$ хүн сууж болно гэсэн үг) багтаамжтай юм.

Эхлээд цахилгаан шат нэг давхарт байна. Мөн цахилгаан шат $a$-р давхраас $b$-р давхар хүрэхэд $|a - b|$ секунд зарцуулдаг (бид хүмүүсийн цахилгаан шатыг унтраах болон асаах цагийг тооцохгүй).

Бүх хүмүүсийг зохих давхарт буулгасны дараа цахилгаан шат буцаад нэг давхарт очиход хамгийн багадаа хэдэн секунд зарцуулах вэ?

Оролт

Эхний мөр нь $n$, $k$ $(1 ≤ n, k ≤ 2000)$ хоёр бүхэл тоог агуулна. Энэ нь хүмүүсийн тоо болон цахилгаан шатны багтаамж юм.

Дараагийн мөр нь $n$ ширхэг $f_{1}, f_{2}, ..., f_{n}$ $(2 ≤ f_{i} ≤ 2000)$ бүхэл тоонууд агуулна. $f_{i}$ нь $i$-р давхарт буух хүмүүсийн тоо юм.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ бол зорилгодоо хүрэхэд шаардлагатай хамгийн бага хугацаа.

Орчуулсан: Даариймаа

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

Оролт
3 2
2 3 4
Гаралт
8
Оролт
4 2
50 100 50 100
Гаралт
296
Оролт
10 3
2 2 2 2 2 2 2 2 2 2
Гаралт
8

Тэмдэглэл

Эхний жишээний хамгийн оновчтой шийд нь:

  1. $1$ ба $2$-р хүн цахилгаан шатанд сууна.
  2. 2-р давхарлуу явна.
  3. Хоёр хүн хоёулаа цахилгаан шатнаас гарна.
  4. Цахилгаан шат буцаад 1-р давхар луу явна.
  5. Дараа нь цахилгаан шатанд $3$-р хүн сууна.
  6. 2-р давхар луу явна.
  7. $2$-р хүн нэмэгдэнэ.
  8. Дараа нь 3-р давхар луу явна.
  9. $2$ хүн гарна.
  10. Дараа нь $3$ хүн гарах 4-р давхар луу явна.
  11. Цахилгаан шат буцаад нэг давхар луу явна.
Сэтгэгдлүүдийг ачааллаж байна...