A. Ваня ба Хашаа

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

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

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

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

Ваня болон түүний найзууд $h$ өндөртэй хашааны дагуу алхаж байгаа бөгөөд тэд уг хашааны харуулд харагдахыг хүсэхгүй байв. Үүний тулд эдгээр найзууд тус бүрийн өндөр нь $h$-аас хэтрэхгүй байх хэрэгтэй юм. Хэрэв зарим нэг хүний өндөр $h$-аас их байвал тэрээр харуулд харагдахгүй байхаар доош бөхийж болно. Мөн $i$-р хүний өндөр нь $a_{i}$-тай тэнцүү байв.

Алхаж буй хүний өргөн нь $1$-тэй тэнцүү гэж үзнэ үү. Харин доош бөхийсөн хүний өргөн нь $2$-той тэнцүү байна. Найзууд нь алхангаа бие биетэйгээ ярилцахыг хүссэн ба иймд тэд нэг эгнээнд алхахыг хүсэж байв. Найзууд нь нэг мөрөнд алхангаа харуулд харагдахгүй байх хамгийн бага замын өргөнийг олно уу?

Оролт

Эхний мөрөнд харгалзан найзуудын тоо болон хашааны өндрийг илэрхийлэх 2 бүхэл тоо $n$ болон $h$ ($1 ≤ n ≤ 1000$, $1 ≤ h ≤ 1000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 2h$)-ууд өгөгдөх ба эдгээрийн $i$-р тоо нь $i$-дахь хүний өндөртэй тэнцүү байна.

Гаралт

Найзуудын алхаж буй замын боломжит хамгийн бага өргөнийг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээнд $3$ дугаартай хүн нь заавал доош бөхийх хэрэгтэй ба ингэснээр шаардлагатай замын өргөн нь $1 + 1 + 2 = 4$ байна.

2-дахь жишээнд бүх найзууд нь хангалттай намхан ба хэн ч бөхийх хэрэггүй юм. Иймд замын өргөн нь $1 + 1 + 1 + 1 + 1 + 1 = 6$ байхад хангалттай байна.

3-дахь жишээнд сүүлийн найзаас бусад бүх хүмүүс доош бөхийх хэрэгтэй байна. Иймд шаардлагатай замын хамгийн бага өргөн нь $2 + 2 + 2 + 2 + 2 + 1 = 11$-тэй тэнцүү байна.

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