# Na cesti

Na začetku $l$ kilometrske ceste je $n$ oseb. Vsak izmed njih začne hojo s hitrostjo $v_i$ ob nekem času $t_i$, dokler ne prispe na cilj. Predpostavimo, da vsi začnejo hoditi ob svojem času (nihče drug ne začne ob istem) in da na cilj prispejo ob različnih časih.

Če se osebi $i$ in $j$ srečata na poti, se spoprijateljita. Natančneje (matematično) velja, da se osebi $i$ in $j$ srečata, če velja, da $t_i < t_j$ in $l/v_i + t_i > l/v_j + t_j$.

Poišči moč (število elementov) največje množice oseb, ki so med seboj prijatelji.

## Vhod

V prvi vrstici standardnega vhoda se nahajata s presledkom ločeni naravni števili $l$ in $n$. V vsaki od naslednjih $n$ vrstic se nahajata celi pozitivni števili $t_i$ in $v_i$.

## Izhod

Na standardni izhod izpiši celo število, ki je enako moči največje množice ljudi, ki so lahko med seboj prijatelji.

## Omejitve in podnaloge

Pri vseh podnalogah velja:

- $100 \leq l \leq 1000$
- $1 \leq n \leq 500$
- $0 \leq t_i \leq 1000$
- $1 \leq v_i \leq 100$

1. podnaloga (17 točk): $n \leq 40$ in rezultat je lahko največ $6$.
2. podnaloga (14 točk): $n \leq 150$ in rezultat je lahko največ $12$.
3. podnaloga (13 točk): $n \leq 250$ in rezultat je lahko največ $16$.
4. podnaloga (25 točk): $n \leq 350$ in rezultat je lahko največ $22$.
5. podnaloga (31 točk): ni dodatnih omejitev

## Primeri

### 1. primer

Vhod:

1000 4
1 3
2 1
0 2
3 4

Izhod:

3

Komentar:

V tem primeru imamo cesto dolžine $l = 1000$ in $4$ osebe, za katere velja:
1. oseba: $t_1 = 0$ in $v_1 = 2$
2. oseba: $t_2 = 1$ in $v_2 = 3$
3. oseba: $t_3 = 2$ in $v_3 = 1$
4. oseba: $t_4 = 3$ in $v_4 = 4$

Tedaj se 1. in 2. oseba srečata (in postaneta prijatelja), ker je $1000/2 + 0 > 1000/3 + 1$.
Z malo računanja ugotovimo še, da se 4. oseba sreča z vsemi ostalimi 3, zato vemo, da so med seboj prijatelji osebe 1, 2 in 4.