GR-H2. Startap

Startapning boshlang‘ich kapitali W. n ta loyiha bor: i-loyihani boshlash uchun kapital kamida cᵢ bo‘lishi kerak (pul sarflanmaydi, faqat talab), tugagach kapitalga pᵢ foyda qo‘shiladi. Ko‘pi bilan K ta loyihani birin-ketin bajarish mumkin, har birini bir marta. Oxirida kapital eng ko‘pi bilan qancha bo‘ladi?

Kirish ma’lumotlari

Birinchi qatorda n, K, W. Keyingi n qatorda cᵢ pᵢ.

Chiqish ma’lumotlari

Bitta son — eng katta kapital.

Cheklovlar

1 ≤ K ≤ n ≤ 2·10⁵; 0 ≤ W, cᵢ ≤ 10⁹; 1 ≤ pᵢ ≤ 10⁴.