tarabe

Sile Marele Cumpărător (SMC) a plecat la piaţă! El ştie că piaţa este formată din N tarabe, fiecare tarabă având spre vânzare o infinitate de produse. De asemenea, SMC ştie preţul iniţial $A_i$ al produsului de la taraba i şi raţia $B_i$ cu care acest preţ creşte o dată cu fiecare cumpărare a unui produs. Cu alte cuvinte, dacă primul produs cumpărat de la taraba i va avea costul $A_i$, al doilea va avea costul $A_i+B_i$, al treilea va avea costul $A_i+2 \cdot B_i$ etc.

Cerinţă

SMC doreşte să cumpere K produse, astfel încât suma preţurilor produselor cumpărate să fie minimă. Deoarece SMC nu ştie aritmetică, voi trebuie să îl ajutaţi, scriindu-i un program!

Date de intrare

Pe prima linie a fişierului tarabe.in se găsesc două numere naturale N şi K, reprezentând numărul de tarabe şi numărul de produse pe care SMC vrea să le cumpere, despărţite printr-un spaţiu. Urmează N linii, pe cea de-a i-a linie fiind scrise două numere naturale $B_i$ şi $A_i$ reprezentând raţia, respectiv costul iniţial al unui produs la taraba i.

Date de ieşire

Pe prima şi singura linie a fişierului de ieşire tarabe.out trebuie să afişaţi un singur număr, respectiv suma minimă a preţurilor pe care o poate obţine SMC dacă va cumpara exact K produse.

Restrictii şi precizări

• 1 <= N <= 200 000;
• 1 <= K <= 1 000 000 000;
• $1 <= A_i, B_i <= 1 000$;
• Pentru 20% din teste N, K <= 1 000;
• Pentru 60% din teste N, K <= 200 000;
• Atenţie! SMC garantează că pentru rezultat pot fi folosite tipuri de date pe 64 de biţi cu semn.

Exemplu

tarabe.in

4 7
9 3
10 2
5 2
4 10

tarabe.out

48

Explicaţie

În ordine, produsele cumpărate vor fi: de la taraba 3 cu costul 2, de la tabara 2 cu costul 2, de la taraba 1 cu costul 3, de la taraba 3 cu costul 2+5, de la taraba 4 cu costul 10, de la taraba 3 cu costul 2+5+5 și de la taraba 2 cu costul 2+10.

Nu există nicio altă variantă care să asigure o sumă mai mică a preţurilor