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