| Fişierul intrare/ieşire: | vrejuri.in, vrejuri.out | Sursă | Algoritmiada 2010, Runda 1 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Vrejuri
Ofelia are in gradina N vrejuri magice, fiecare avand o anumita inaltime Hi. Problema este ca vrejurile au inceput sa creasca, astfel, fiecare planta i isi va mari inaltimea cu Pi zilnic. Ofelia stie ca vrejurile vor creste doar in urmatoarele K zile iar dupa aceea se vor opri, si vrea ca la sfarsitul celor K zile suma inaltimilor tuturor vrejurilor sa fie cel mult S. Pentru aceasta, ea are o foarfeca magica cu ajutorul careia, la sfarsitul fiecarei zile, poate reduce inaltimea fiecarui vrej i cu xi. Dar foarfeca magica nu este usor de folosit, astfel pentru a taia o anumita valoare xi din vrejul i efortul depus este xi2 Jouli (Ofelia se pricepe la fizica, dar, bineinteles, nu si la informatica). Ofelia vrea sa afle care este efortul total minim J (suma tuturor eforturilor depuse in procesele de taiere), pe care il poate depune pentru ca suma inaltimilor vrejurilor la sfarsitul celor K zile sa fie cel mult S.
Date de intrare
Fişierul de intrare vrejuri.in va contine pe prima linie numerele N, K si S. Urmatoarele N linii vor contine fiecare cate doua numere Hi si Pi reprezentand inaltimea initiala a vrejului i si respectiv, rata cu care acesta creste.
Date de ieşire
În fişierul de ieşire vrejuri.out veti afisa un singur numar J efortul minim pe care Ofelia il poate depune.
Restricţii
- 1 ≤ N, K ≤ 100 000
- 0 ≤ S ≤ 1018
- 1 ≤ Hi, Pi ≤ 109
- Se garanteaza ca rezultatul J nu va depasi 1018
- Se garanteaza ca suma inaltimilor tuturor vrejurilor netaiate la sfarsitul celor K zile nu va depasi 1018
- Atentie: Ofelia poate taia doar dupa ce prima zi se incheie. Adica vrejurile cresc in prima zi si abia apoi Ofelia poate taia din ele
- Atentie: La sfarsitul fiecarei zile Ofelia poate taia orice valoare din oricate plante. Ea poate taia valori diferite din plante diferite in zile diferite.
- Chiar daca o planta este taiata pana la inaltimea 0, ea tot va creste in urmatoarea zi (radacina nu se scoate).
Exemplu
| vrejuri.in | vrejuri.out |
|---|---|
| 2 2 1 1 1 2 2 | 18 |
Explicaţie
Ofelia poate taia in prima zi 1 din primul vrej si 2 din al doilea, iar in a doua zi 2 din primul si 3 din al doilea. Costul total este 18.
