== include(page="template/taskheader" task_id="cadouri") ==

Pentru că Lili a uitat să îi dea un cadou de Crăciun prietenei ei, Georgiana, s-a gândit să se revanşeze aducându-i cadouri timp de $N$ zile. Astfel, în fiecare zi $i$ din cele $N$, Lili va duce în faţa casei Georgianei $cnt{~i~}$ cadouri, toate de mărime $m{~i~}$. După cele $N$ zile, Georgiana se apucă să sorteze cutiile cu cadouri în ordine crescătoare după mărime. Deoarece s-au strâns foarte multe cadouri, Georgiana te roagă să afli mărimea celui de al $K$-lea cadou după sortare.

Poveste şi cerinţă...

h2. Date de intrare

Vă rugăm să consultaţi fişierul _$manager.cpp$_ pe care îl puteţi găsi în ataşamente.

Fişierul de intrare $cadouri.in$ ...

h2. Date de ieşire

În fişierul de ieşire $cadouri.out$ se va afişa un singur număr, mărimea celui de-al $K$-lea cadou în ordinea sortării.
 
h2. Notă
 
Între ataşamente, puteţi găsi fişierul _$manager.cpp$_ pe care îl puteţi descărca. E recomandat, atât pentru a scrie o sursa eficientă şi elegantă, cât şi pentru a simula experienţa problemei din timpul concursului, să completaţi această sursă cu implementarea funcţiei $solve()$.

În fişierul de ieşire $cadouri.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 5 000 000$
* $1 ≤ cnt{~i~}, m{~i~} ≤ 10^9^$, pentru orice $i$ de la $0$ la $N - 1$
* <tex> $1 \leq K \leq \sum_{i=0}^{N-1} cnt_i$ </tex>
* Pe testele oficiale, şirurile $cnt$ şi $m$ sunt generate pseudo-random. Detaliile sunt ascunse concurenţilor.
* Testele sunt grupate pe subtaskuri. Punctele pe un subtask sunt acordate doar dacă sursa trece toate testele din respectivul subtask. Punctajele pe subtaskuri diferă de cele din concurs.
* Subtask 1, în valoare de $15$ puncte, <tex> $\sum_{i=0}^{N-1} cnt_i \leq 5\ 000\ 000$ </tex>
* Subtask 2, în valoare de $15$ puncte, $N &le; 50 000$
* Subtask 3, în valoare de $15$ puncte, $K = 4$
* Subtask 4, în valoare de $30$ puncte, $1 &le;  m{~i~} &le; 3$, pentru orice $i$ de la $0$ la $N - 1$
* Subtask 5, în valoare de $25$ puncte, fără restricţii suplimentare

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. cadouri.in |_. cadouri.out |

|5 7
3 2
4 3
2 1
2 2
1 1
|2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Mărimile cadourilor, după sortare, sunt:
$1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3$
 
Prin urmare cadoul al $7$-lea în ordinea sortării are mărimea $2$.

...

== include(page="template/taskfooter" task_id="cadouri") ==