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

Poveste şi cerinţă...

Coloniile de gandaci au fost dintotdeauna in centrul atentiei oamenilor de stiinta.
Prin avansuri tehnologice, reusim acum sa descriem o colonie de gandaci printr-un numar care este "gradul" coloniei.
Coloniile de grad $0$ si $1$ reprezinta un gandac baiat respectiv un gandac fata, si coloniile de grad $i > 1$ sunt compuse din unirea unei colonii de grad $i - 1$ si altei colonii de grad $i - 2$.
 
Astfel, primele cateva colonii sunt urmatoarele:
Colonia 0: un baiat
Colonia 1: o fata
Colonia 2: un baiat si o fata
Colonia 3: un baiat si doua fete
...
 
Tu esti proprietarul celei mai mari crescatorii de gandaci din lume, avand la dispozitie un numar relativ infinit de colonii de orice grad.
 
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?

h2. Date de intrare

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

Fişierul de intrare $fibonaccibug.in$ contine pe prima linie numarul $T$ de teste.
Urmeaza cele $T$ teste.
Prima linie a fiecarui test contine numerele $N$ si $K$.
Urmatoarele $N$ linii a fiecarui test contin cele doua numere $Ai$ si $Bi$.

h2. Date de ieşire

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

În fişierul de ieşire $fibonaccibug.out$ se vor afisa T linii, a $i$-a linie continand raspunsul pentru al $i$-lea test.

h2. Restricţii

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

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

h2. Exemplu