시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

Consider a road of length ℓ. There are n persons. The ith person, i = 1, . . . , n, will start walking from the beginning of the road at time ti and will move at a constant speed vi until arrival at the end of the road. We assume no two persons start walking at the same time, and no two persons arrive at the same time.

If the ith and jth person meet each other on the road, they will become friends. Mathematically, for the ith and jth persons where ti < tj, they will become friends if and only if ℓ/vi + ti > ℓ/vj + tj.

Your task is to find the size of the maximum set of persons who are friends of each other.

입력

Your program must read from the standard input. The input consists of n+1 lines. The first line contains two integers ℓ and n separated by space, where 100 ≤ ℓ ≤ 10000 and 1 ≤ n ≤ 500. Each of the next n lines contains two integers. For the (i+1)-th line, it contains the two integers ti and vi separated by space, where 0 ≤ ti ≤ 1000 and 1 ≤ vi ≤ 100.

출력

Your program must write to the standard output an integer which is the size of the maximum set of persons who are friends of each other.

예제 입력 1

1000 4
1 3
2 1
0 2
3 4

예제 출력 1

3

Suppose the length of the road is ℓ = 1000, there are 4 persons who start walking at time t1 = 0, t2 = 1, t3 = 2 and t4 = 3 respectively, and their walking speeds are v1 = 2, v2 = 3, v3 = 1 and v4 = 4 respectively.

Then, the 1st person will meet with the 2nd person since 1000/2+0 > 1000/3+1. Similarly, we have the following table.

  1st 2nd 3rd 4th
1st   friend not friend friend
2nd     not friend friend
3rd       friend

Hence, the 1st, 2nd and 4th persons are friends of each other. In fact, this is the maximum set. We report 3 to be the size of the maximum set of persons who are friends of each other.

예제 입력 2

1000 4
0 1
2 1
1 1
3 1

예제 출력 2

1

Suppose the length of the road is ℓ = 1000, there are 4 persons who start walking at time t1 = 0, t2 = 1, t3 = 2 and t4 = 3 respectively and their walking speeds are v1 = 1, v2 = 1, v3 = 1 and v4 = 1 respectively.

Then, none of them will meet each other. Hence, we report 1 to be the size of the maximum set of persons who are friends of each other.