Fişierul intrare/ieşire:tarabe.in, tarabe.outSursăONI 2012 - clasele 11-12
AutorAndrei Parvu, Bogdan-Cristian Tataroiu, Mugurel Ionut Andreica, Tiberiu SavinAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.8 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/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 Ai al produsului de la taraba i şi raţia Bi 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 Ai, al doilea va avea costul Ai + Bi, al treilea va avea costul Ai + 2*Bi 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 Bi şi Ai 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 ≤ Ai, Bi ≤ 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.intarabe.outExplicaţie
4 7
9 3
10 2
5 2
4 10
48
Î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 si de la taraba 2 cu costul 2+10.
Nu există nicio altă variantă care sa asigure o sumă mai mică a preţurilor
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content