9828번 - Walking 다국어

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 t_i and will move at a constant speed v_i 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 t_i < t_j, they will become friends if and only if ℓ/v_i + t_i > ℓ/v_j + t_j.

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 t_i and v_i separated by space, where 0 ≤ t_i ≤ 1000 and 1 ≤ v_i ≤ 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.