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 in fiecare zi. Ofelia stie ca vrejurile vor creste doar in urmatoarele K zile 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 depasia 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 orice si oricate plante. Ea poate taia valori diferite din plante diferite in zile diferite.
Exemplu
| vrejuri.in | vrejuri.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
