Maximum Distinct Jump Balls

There is an infinite vertical grid where the positive direction of the x-axis is from left to right and the positive direction of the y-axis is from bottom to top. On this plane there are n distinct jump balls, each of which can be used infinitely many times. When kid stands exactly at the position of a jump ball, he may press the shift key and then will instantly ascend by \(d\) units (this jump is purely vertical with no horizontal movement). After jumping, he falls downward at a rate of 1 unit per second. In each following second, while falling, kid can optionally move horizontally by 1 unit to the left or right or not move at all. When kid is not on a jump ball, he cannot initiate a jump.

Kid starts at the \(c\)-th jump ball (indexed from 1) and may begin by jumping immediately. His score is defined as the number of distinct jump balls from which he has initiated a jump (if he jumps from the same ball multiple times it is counted only once). Note that his movement mechanics are different from those in the iw game. Also, kid’s position always remains at integer coordinates.

Given these rules, compute the maximum score kid can achieve. It is not necessary (but allowed) for kid to ever return to his starting jump ball.

Jump Condition: Suppose kid is on a jump ball at \((x_i, y_i)\). When he jumps, his vertical position instantly becomes \(y_i + d\). After exactly \(T\) seconds of falling (with \(T \ge 0\)), his vertical coordinate becomes \(y_i + d - T\). In order to land on another jump ball at \((x_j, y_j)\), it is necessary that \(T = y_i + d - y_j \ge 0\) and that the horizontal distance satisfies \(|x_j - x_i| \le T\).

inputFormat

The first line contains three integers \(n\), \(d\) and \(c\) (number of jump balls, jump height and starting ball index respectively). \(1 \le c \le n\).

The next \(n\) lines each contain two integers \(x\) and \(y\), representing the coordinates of a jump ball. It is guaranteed that all jump balls are distinct.

outputFormat

Output a single integer, the maximum score kid can achieve.

sample

3 2 1
0 0
1 0
0 1

3