Walking

Interview

Time limit1sMemory limit128 MB

Summary

Walkers start at distinct times with fixed speeds, and a later starter who arrives earlier befriends the other; find the largest group where every pair meets.

Level: Medium4 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

Consider a road of length $\ell$ . There are $n$ persons. The $i$ th person, for $i = 1, \ldots, n$ , starts walking from the beginning of the road at time $t_i$ and moves at a constant speed $v_i$ until arrival at the end of the road. No two persons start walking at the same time, and no two persons arrive at the same time.

If the $i$ th and the $j$ th person meet each other on the road, they become friends. Written as a formula, for two persons $i$ and $j$ with $t_i < t_j$ , they become friends if and only if $\ell / v_i + t_i > \ell / v_j + t_j$ .

Find the size of the largest set of persons who are all friends of each other.

Input

Your program must read from the standard input. The input consists of $n + 1$ lines. The first line contains two integers $\ell$ and $n$ separated by a single space, where $100 \le \ell \le 10000$ and $1 \le n \le 500$ . Of the next $n$ lines, line $i + 1$ contains two integers $t_i$ and $v_i$ separated by a single space, where $0 \le t_i \le 1000$ and $1 \le v_i \le 100$ .

Output

Your program must write one integer to the standard output. That integer is the size of the largest set of persons who are all friends of each other.

Examples2

Example 1
Input
```
1000 4
1 3
2 1
0 2
3 4
```
Expected output
```
3
```
Example 2
Input
```
1000 4
0 1
2 1
1 1
3 1
```
Expected output
```
1
```