GR-H9. Arzon yoqilg‘i

Yuk mashinasi 0 nuqtadan D km uzoqdagi omborga boradi, 1 km ga 1 litr sarflaydi. Bak hajmi C litr, boshida bak to‘la. Yo‘lda n ta shoxobcha bor: i-si xᵢ km da, litri pᵢ so‘m; har birida istalgancha (bak sig‘guncha) olish mumkin. Omborga yetish uchun eng kam xarajat qancha? Iloji bo‘lmasa — -1.

Kirish ma’lumotlari

Birinchi qatorda D, C, n. Keyingi n qatorda xᵢ pᵢ (xᵢ o‘sish tartibida).

Chiqish ma’lumotlari

Bitta son — eng kam xarajat yoki -1.

Cheklovlar

1 ≤ D, C ≤ 10⁹; 0 ≤ n ≤ 2·10⁵; 0 < x₁ < … < xₙ < D; 1 ≤ pᵢ ≤ 10⁶.