BS-M3. Yuk kemasi

Portda n ta yuk navbatda turibdi, i-yukning og‘irligi wᵢ tonna. Kema har kuni navbatdagi yuklarni ketma-ket oladi (tartib o‘zgarmaydi, yukni bo‘lib bo‘lmaydi), kunlik yuki esa kema sig‘imidan oshmasligi kerak. Hamma yukni D kunda tashib bo‘lish uchun kema sig‘imi eng kamida qancha bo‘lishi kerak?

Sig‘im C berilsa, nechta kun kerakligini ochko‘z usulda bilib olamiz: sig‘may qolguncha yuklaymiz.

Kirish ma’lumotlari

Birinchi qatorda n va D, ikkinchisida n ta og‘irlik.

Chiqish ma’lumotlari

Bitta son — eng kichik sig‘im.

Cheklovlar

1 ≤ D ≤ n ≤ 10⁵; 1 ≤ wᵢ ≤ 10⁶.