Kingdom Trip

The kingdom is an infinite flat plane with no borders. It holds $n$ gathering locations.

The king wanted a closer look at his people, so he planned a trip through all of them with a speech at each one. The original plan is the polygonal chain $p_1 \to p_2 \to \cdots \to p_n$.

The king is old, so his assistants want to cut the number of speeches by skipping some locations. The new plan has to be a polygonal chain over a subsequence of $p$ that starts at $p_1$ and ends at $p_n$, that is, $p_{i_1} \to p_{i_2} \to \cdots \to p_{i_m}$ with $1 = i_1 < i_2 < \cdots < i_m = n$.

A location $p_j$ with $i_k < j < i_{k+1}$ can be skipped only if the distance from $p_j$ to the segment $p_{i_k} p_{i_{k+1}}$ is at most $d$. If that distance exceeds $d$, the king refuses to drop the location.

Find the new route with the smallest possible number of locations.

The first line contains two integers $n$ and $d$ ($2 \le n \le 2000$, $1 \le d \le 10^6$). Here $n$ is the number of locations in the original plan and $d$ is the largest distance allowed to a skipped location.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$, the coordinates of location $p_i$. The absolute value of each coordinate is at most $10^6$, and no two locations share the same coordinates.

Print the smallest number of locations the king visits. The answer is guaranteed to be the same when $d$ grows or shrinks by $10^{-4}$.