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 castiga maxim intr-o zi?

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

h2. Date de intrare

h2. Restricţii

* $1 ≤ T, N, K, Ai ≤ 100.000$
* Suma tuturor $N$-urilor nu va depasi $100.000$.
* $1 ≤ Bi ≤ 10^9^$

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

h2. Exemplu
table(example). |_. fibonaccibug.in |_. fibonaccibug.out |

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

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

|
h3. Explicaţie

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

...

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