h2. Date de intrare

Fişierul de intrare $cadouri.in$ conţine pe prima linie 2 numere naturale $N$ şi $K$, cu semnificaţia din enunţ. Următoarele $N$ linii conţin câte 2 numere, $cnt{~i~}$ şi $m{~i~}$, separate prin câte un spaţiu, reprezentând descrierea cadourilor din ziua $i$.

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

h2. Date de ieşire

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