- Special Robot的程序的编写思路
Bob invented a special kind of robot controlled by a remote controller. The interesting thing is that the robot can only move in a 2-dimentional plane which is vertical to the ground. Now we assume the vertical plane can be shown in Figure 1.
Now Bob wants to conduct a performance for his robot. The situation can be described as follows: n balloons stay still on the ground; all of these balloons have an initial position whose Y-coordinates are 0.
Each balloon will move up at certain time. The initial position of the robot is at (0, 0) and if the robot is at position (x, y) at time t, then it can only move to position (x, y-1) or position (x+1, y+1) in a unit time (the robot con not stay still at a position). Its task is to collect as more balloons as possible when it gets to the destination (K,0).
When the robot is moving on the plane, balloons are continuously rising on its path from the ground. Each balloon can reach a unit height in a unit time.
When the robot meets a balloon, it collects the balloon. The situation can be described as the following three examples which are shown in Figure 2:
Example 1: At time t, the robot is at position (x, y), and a balloon is at position (x, y-2). The robot moves down and the balloon moves up; then at time t+1, the robot and the balloon meet at position (x, y-1), so the balloon can be collected by the robot ( which is shown in Figure 2(a)).
Example 2: At time t, there is a balloon at position (x, y-1) and the robot stands at position (x, y). Because the balloon always moves up and the robot can move down, so the robot can collect this balloon because they will meet at some point between position (x, y-1) and (x, y) during their movement (which is shown in Figure 2(b)).
Example 3: At time t, a balloon is at position (x+1, y) and the robot is at position (x, y). Because the robot can arrive at position (x+1, y+1) while the balloon can move up to the same position, the robot could collect the balloon at time t+1 (which is shown in Figure 2(c)).
Maybe it is too easy a problem to control one robot, so Bob intends to control two robots simultaneously.
You need to help him to calculate the maximum balloons these two robots can collect when they get to the destination.
It is possible that the two robots get to the same position at the same time. Note that one balloon could not be collected by two robots and the balloons staying on the ground could not be collected either.
Robot should not move to the underground (y < 0).
The input contains several cases. For each case, the first line gives the value of n (0 ≤ n ≤ 10,000) and K (1 ≤ K ≤ 100) followed by n lines in which each contains two integers x (1 ≤ x ≤ K) and t (0 ≤ t ≤ 1000).
The first integer indicates the position of a balloon and the other indicates the beginning time for it to rise. In the value of n and K, n is the number of balloons and K is the x-coordinate of the destination. The input is ended by two zeros.
For each case, output the maximum balloons the two robots can collect.