BS-O5. Yo‘l puli

Mamlakatda n ta shahar va m ta ikki tomonlama pullik yo‘l bor: i-yo‘l uzunligi lᵢ km, undan o‘tish puli cᵢ so‘m. Haydovchi 1-shahardan n-shaharga jami ko‘pi bilan D km yo‘l bosib borishi kerak. Yo‘lda to‘lanadigan eng katta bir martalik pul imkon qadar kichik bo‘lsin — shu summani chiqaring. Yetib bo‘lmasa — -1; n = 1 bo‘lsa — 0.

Pul chegarasi C berilsa, faqat cᵢ ≤ C yo‘llar bo‘yicha eng qisqa masofani Deykstra topadi.

Kirish ma’lumotlari

Birinchi qatorda n, m, D. Keyingi m qatorda yo‘l: u v l c.

Chiqish ma’lumotlari

Bitta son — eng katta pulning eng kichik qiymati yoki -1.

Cheklovlar

1 ≤ n ≤ 10⁴; 1 ≤ m ≤ 3·10⁴; 1 ≤ lᵢ ≤ 10⁶; 1 ≤ cᵢ ≤ 10⁹; 1 ≤ D ≤ 10¹⁴.