Fişierul intrare/ieşire:	dlboss.in, dlboss.out	Sursă	FMI No Stress 2017
Autor	Miriam Costan	Adăugată de	Fmi No Stress 7 •fmins7
Timp execuţie pe test	0.25 sec	Limită de memorie	66048 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dl. Boss

Din domnişoară în domnişoară

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ă.

Date de intrare

Pe prima linie a fişierului dlboss.in se găseşte un număr întreg N, reprezentând numărul de domnişoare. Pe a doua linie se găseste T, timpul în minute alocat pentru vizite. Următoarele N linii conţin câte două numere întregi seperate prin câte un spaţiu care descriu timpul pierdut cu fiecare fată şi coeficientul de frumuseţe al acesteia. 

Date de ieşire

În fişierul de ieşire dlboss.out se vor găsi N linii, linia i reprezentând numărul maxim de fete pe care Dl. Boss le poate vizita dacă porneşte vizitele de la dominşoara cu indicele de ordine i. 

Restricţii

• 1 ≤ N ≤ 100.000
• Coeficienţii de frumuseţe sunt numere întregi între 1 şi 10⁹
• 1 ≤ T ≤ 10⁹
• 1 ≤ t[i] ≤ 10⁴
• 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ţă.

Exemplu

Cum se trimit solutii?