== include(page="template/taskheader" task_id="tarabe") ==
Poveste şi cerinţă...
p<>. 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.
h2. Cerinţă
p<>. $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!
h2. Date de intrare
Fişierul de intrare $tarabe.in$ ...
p<>. 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$.
h2. Date de ieşire
În fişierul de ieşire $tarabe.out$ ...
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.
h2. 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.
h2. Exemplu
table(example). |_. tarabe.in |_. tarabe.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
h2. Exemplu
...
table(example). |_. tarabe.in |_. tarabe.out |_. Explicaţ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
|
== include(page="template/taskfooter" task_id="tarabe") ==
