== include(page="template/taskheader" task_id="vrejuri") ==

Poveste şi cerinţă...

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 $xi^2^$ 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$.

h2. Date de intrare

Fişierul de intrare $vrejuri.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $vrejuri.out$ ...

În fişierul de ieşire $vrejuri.out$ veti afisa un singur numar $J$ efortul minim pe care Ofelia il poate depune.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, K ≤ 100 000$
* $1 ≤ S ≤ 10^18^$
* $1 ≤ Hi, Pi ≤ 10^96$
 

h2. Exemplu