Astazi ai primit $N$ comenzi, fiecare caracterizate prin doua numere $Ai$ si $Bi$, semnificand ca poti vinde oricate colonii de tipul $Ai$ la $Bi$ bani fiecare.
Din pacate, din cauza legilor anti monopol asupra gandacilor, nu ai voie sa vinzi mai mult de $K$ gandaci pe zi (vinderea unei colonii este echivalenta cu vinderea tuturor gandacilor din aceasta).

Daca iti alegi in mod optim ce comenzi sa procesezi, cati bani poti gasiga maxim?

Daca iti alegi in mod optim ce comenzi sa procesezi, cati bani poti castiga maxim intr-o zi?

h2. Date de intrare

h2. Restricţii

* $1 ≤ T, N, Ai ≤ 100.000$

* $1 ≤ T, N, K, Ai ≤ 100.000$

* Suma tuturor $N$-urilor nu va depasi $100.000$.
* $1 ≤ Bi ≤ 10^9^$
h2. Exemplu
table(example). |_. fibonaccibug.in |_. fibonaccibug.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
5 11
1 2
2 2
3 5
4 9
5 50
| 56

|
h3. Explicaţie

...

Optim este sa alegem a $5$-a oferta si de $3$ ori prima oferta.

== include(page="template/taskfooter" task_id="fibonaccibug") ==