Revizia anterioară Revizia următoare
| 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 minim J, 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
- 1 ≤ S ≤ 1018
- 1 ≤ Hi, Pi ≤ 109
- Se garanteaza ca rezultatul J nu va depasi 1018
- Atentie: Ofelia poate taia doar dupa ce prima zi se incheie. Adica vrejurile cresc cel putin odata 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 |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
