campion

Campion

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

Poveste si cerinta...

Zaharel lucreaza din greu la site-ul 'infoarena 2.0':http://infoarena.ro. Treaba lui este sa construiasca un sistem de rating al utilizatorilor, in functie de competitiile la care a participat fiecare.
 
In primul rand, va trebui sa numere cati concurenti au fost campioni pe parcursul timpului. Pentru a simplifica problema, vom considera momentele de timp ca fiind numere *reale* intre $0$ si $T$.
 
Fiecare din cei $N$ utilizatori infoarena au inceput sa concureze la timpul $0$ si au avut un rating $R{~i~}$ $(1 ≤ i ≤ N)$. Se stie, de asemenea, ca fiecare concurent isi imbunatateste rating-ul cu $D{~i~}$ $(1 ≤ i ≤ N)$ pentru fiecare unitate de timp care trece.
 
Un utilizator se numeste campion daca exista un moment de timp in care a avut cel mai mare rating dintre toti utilizatorii. Daca doi sau mai multi utilizatori au fiecare cel mai mare rating intr-un moment de timp, se considera ca toti sunt campioni.
 
h2. Cerinta
 
Ajutati-l pe Zaharel sa determine numarul de utilizatori care au fost campioni.

h2. Date de intrare

...

In fisierul $campion.in$ se afla pe prima linie numerele naturale $N$ si $T$ reprezentand numarul de utilizatori si limita superioara a momentelor de timp. Urmeaza $N$ linii fiecare continand doua numere naturale $R{~i~}$ $D{~i~}$, reprezentand rating-ul initial si valoarea cu care se imbunatateste per unitate de timp, al fiecarui utilizator.

h2. Date de iesire

...

Fisierul de iesire $campion.out$ va contine o singura linie pe care se va afla numarul de concurenti care au fost campioni.

h2. Restrictii

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

* $1 ≤ N ≤ 20 000$
* $0 ≤ T ≤ 100 000 000$
* $0 ≤ R{~i~} ≤ 1 000 000 000$
* $0 ≤ D{~i~} ≤ 1 000 000$
* Rating-ul fiecarui utilizator nu va depasi $2 000 000 000$ pentru orice moment de timp din intervalul $[0...T]$
* Toatele numerele din fisierul de intrare sunt numere naturale
* Pot exista utilizatori cu acelasi rating de inceput si aceasi valoare de imbunatatire

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

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

| 3 6
20 0
4 2
15 1
| 2

|
h3. Explicatie

...

Concurentul $1$ este initial campion, iar la momentul $5$ concurentul $3$ devine campion. Concurentul $2$ devine campion la momentul $11$, dar $T = 6$, deci nu se ia in considerare.

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

1695