걷기 Batch 컴파일 명령

길이가 $\l$인 도로를 생각해 봅시다. $n$명의 사람이 있습니다. $i$번째 사람은 ($i=1, \cdots, n$) $t_{i}$의 시각에 도로의 왼쪽 끝에서 걷기 시작해서 $v_{i}$의 속도로 도로 오른쪽 끝에 도착할 때까지 움직입니다. 어떤 두 사람도 동시에 걷기 시작하거나 동시에 도착할 일은 없다고 가정합시다.

$i$번 사람과 $j$번 사람이 도로에서 만난다면, 그들은 친구가 될 것입니다. 수학적으로, $t_{i} < t_{j}$를 만족하는 두 $i, j$에 대해, $l / v_{i} + t_{i} > l / v_{j} + t_{j}$는 이 $i$번 사람과 $j$번 사람이 친구가 될 필요충분조건입니다.

여러분이 할 일은 이 $n$명의 사람들로 구성된 집합들 중 서로 친구인 집합의 최대 크기(원소의 수)를 구하는 것입니다.

입력 형식

첫 번째 줄에 두 개의 정수 $l$과 $n$이 주어집니다. ($100 \le l \le 10000, 1 \le n \le 500.$) 다음 $n$개 줄에는 두 개의 정수가 주어집니다. $(i+1)$번째 줄에 두 개의 정수 $t_{i}$와 $v_{i}$가 주어집니다. (단 $0 \le t_{i} \le 1000, 1 \le v_{i} \le 100.$)

출력 형식

서로 친구인 사람들의 집합들 중 가장 큰 집합의 크기(원소의 수)를 출력합니다.

서브태스크

1. (3점) 사람이 최대 40명 주어집니다. 답은, 즉 서로 친구인 사람들의 집합 중 가장 큰 집합의 크기는 최대 6입니다.
2. (3점) 사람이 최대 150명 주어집니다. 답은 12 이하입니다.
3. (5점) 사람이 최대 250명 주어집니다. 답은 16 이하입니다.
4. (7점) 사람이 최대 350명 주어집니다. 답은 22 이하입니다.
5. (7점) 사람이 최대 500명 주어집니다. 답은 1 이상 500 이하입니다.

예제 1

$l = 1000$이고, 4명의 사람이 $t_{1}=0, t_{2}=1, t_{3}=2, t_{4}=3$의 시간에 출발하고, 그들의 걷기 속도는 $v_{1}=2, v_{2}=3, v_{3}=1, v_{4}=4$라고 가정해 봅시다. 그러면 1번 사람은 2번 사람을 만날 것인데, $1000/2+0 > 1000/3+1$이기 때문입니다. 비슷한 식으로 아래 표를 채울 수 있습니다.

따라서, 1번, 2번, 4번 사람은 서로 친구입니다. 이것이 최대 크기를 가지는 집합이 됩니다. 이 경우 3을 출력해야 합니다.

예제 2

$l = 1000$이고, 4명의 사람이 $t_{1}=0, t_{2}=1, t_{3}=2, t_{4}=3$의 시간에 출발하고, 그들의 걷기 속도는 $v_{1}=2, v_{2}=1, v_{3}=1, v_{4}=1$라고 가정해 봅시다. 그러면 어떤 두 사람도 서로 만날 수 없기 때문에, 최대 집합의 크기는 1이 됩니다.