Fişierul intrare/ieşire:	tarabe.in, tarabe.out	Sursă	ONI 2012 - clasele 11-12
Autor	Andrei Parvu, Bogdan-Cristian Tataroiu, Mugurel Ionut Andreica, Tiberiu Savin	Adăugată de	Simoiu Robert •SpiderMan
Timp execuţie pe test	0.4 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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*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.

Restricţii

• 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

Cum se trimit solutii?