Fişierul intrare/ieşire:	fibonaccibug.in, fibonaccibug.out	Sursă	IIOT 2019-20 Runda 1
Autor	Alexandru Petrescu	Adăugată de	Comisia IIOT 2019-20 •unibucPoli2019
Timp execuţie pe test	0.3 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibonaccibug

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

Date de intrare

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.

Date de ieşire

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

Restricţii

• 1 ≤ T, N, K, Ai ≤ 100.000
• Suma tuturor N-urilor nu va depasi 100.000.
• 1 ≤ Bi ≤ 10⁹

Exemplu

Explicaţie

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

Cum se trimit solutii?