dlboss

Dl Boss

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

Dl. Boss e mare gagicar. Sâmbătă seara a cucerit în club $N$ domnişoare şi le-a promis tuturor că le va vizita a doua zi. Duminică s-a trezit târziu şi a realizat că vizitase deja o tipă dar nu mai ştie pe care. Dl. Boss a decis că va pleca iar de acasă la ora $12$ deci are fix $T$ minute pentru vizite. Ştie exact cât timp va pierde cu fiecare domnişoară, cu tot cu drumul până la ea acasă şi înapoi. După ce vizitează o fată, Dl. Boss vine acasă şi pleacă la următoarea, pentru a nu stârni niciun fel de suspiciune. Dl. Boss le-a atribuit fetelor câte un **coeficient de frumuseţe**. După ce el vizitează pe cineva cu coeficientul $X$ este sub demnitatea lui să viziteze pe cineva cu coeficientul mai mic sau egal decât $X$ (cu alte cuvinte, Dl. Boss va vizita doar fete în ordinea **strict crescătoare** a coneficienţilor de frumuseţe ai acestora).

h3. _Din domnişoară în domnişoară_

În aceste condiţii, Dl. Boss este curios să afle pentru fiecare domnişoară, dacă ea ar fi fost cea deja vizitată, care este numarul maxim de fete pe care le mai poate vizita. Dl. Boss se duce să se pregătească pentru întâlniri. În timpul ăsta, ştiind $t[i]$ - timpul în minute pierdut cu domnişoara $i$ şi $c[i]$ - coeficientul de frumuseţe al domnişoarei $i$, trebuie sa îl ajutaţi pe Dl. Boss să afle câte domnişoare poate vizita maxim începând de la fiecare dintre ele.

Dl. Boss e mare gagicar. Sâmbătă seara a cucerit în club $N$ domnişoare şi le-a promis tuturor că le va face o vizită. Duminică s-a trezit târziu şi a realizat că vizitase deja o tipă norocoasă dar nu mai ştie pe care. Dl. Boss a decis că va pleca iar de acasă la ora $12$ şi are fix $T$ minute pentru vizite. Ştie exact cât timp va pierde cu fiecare domnişoară, cu tot cu drumul până la ea acasă şi înapoi. După ce vizitează o fată, Dl. Boss vine acasă şi pleacă la următoarea, pentru a nu stârni niciun fel de suspiciune. Dl. Boss le-a atribuit fetelor câte un **coeficient de frumuseţe**. După ce el vizitează pe cineva cu coeficientul $X$, este sub demnitatea lui să viziteze pe cineva cu coeficientul mai mic sau egal decât $X$ (cu alte cuvinte, Dl. Boss va vizita doar fete în ordinea **strict crescătoare** a coeficienţilor de frumuseţe ai acestora).
 
În aceste condiţii, Dl. Boss este curios să afle pentru fiecare domnişoară, dacă ea ar fi fost cea deja vizitată, care este numarul maxim de fete pe care le mai poate vizita. Dl. Boss se duce să se pregătească pentru întâlniri. În timpul ăsta, ştiind $t[i]$ - timpul în minute pierdut cu domnişoara $i$ şi $c[i]$ - coeficientul de frumuseţe al domnişoarei $i$, trebuie sa îl ajutaţi pe Dl. Boss să afle câte domnişoare poate vizita maxim oricare ar fi fost cea deja vizitată.

h2. Date de intrare

* $1 ≤ $N$ ≤ 100.000$
* Coeficienţii de frumuseţe sunt numere întregi între $1$ şi $10^9^$

* $1 ≤ $T$ ≤ 10^9$
* $1 ≤ $t[i]$ ≤ 10^4$

* $1 ≤ $T$ ≤ 10^9^$
* $1 ≤ $t[i]$ ≤ 10^4^$
* Atât Dl. Boss, cât şi frumoasele lui domniţe au găsit secretul vieţii veşnice, aşa că nu sunt motive de îngrijorare din nicio privinţă.

h2. Exemplu

450 70
15 5
60 29

| 5
2

| 4
1

6

4

3

2

4

5
0

6

1
7

3
|

h3. Explicaţie
 
...
 

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