Matcom Online Grader

Once upon a time, there was a kingdom ruled by a wise king. After forty three years of his reign, by means of successful military actions and skillful diplomacy, the kingdom became an infinite flat two-dimensional surface. This form of the kingdom greatly simplified travelling, as there were no borders.

A big holiday was planned in the kingdom. There were $n$ locations for people to gather. As the king wanted to have a closer look at his people, he ordered to make a trip through these locations. He wanted to give  a speech in each of these locations.  Initially his trip was designed as a polygonal chain $p$: $p_1 \rightarrow p_2 \rightarrow \ldots \rightarrow p_n$.

Not only the king was wise, but he was old, too. Therefore, his assistants came up with an idea to skip some locations, to make the king to give as few speeches as possible.  The new plan of the trip has to be a polygonal chain consisting of some subsequence of $p$: starting at $p_1$ and ending at $p_n$, formally, $p_{i_1} \rightarrow p_{i_2} \rightarrow \cdots \rightarrow p_{i_m}$, where $1 = i_1 < i_2 < \cdots < i_m = n$. Assistants know that the king wouldn't allow to skip location $j$, if the distance from $p_j$ to segment  $p_{i_k} \rightarrow p_{i_{k+1}}$ exceeds $d$, for such $k$, that $i_k < j < i_{k+1}$.

Help the assistants to find the new route that contains the minimum possible number of locations.

The first line of the input file contains two integers $n$ and $d$ —  the number of locations in the initial plan of the trip and the maximum allowed distance to skipped locations ($2 \le n \le 2000$; $1 \le d \le 10^6$).

The following $n$ lines describe the trip. The $i$-th of these lines contains two  integers $x_i$ and $y_i$ —  coordinates of point $p_i$.  The absolute value of coordinates does not exceed $10^6$.No two points coincide.

Output the minimum number of locations the king will visit. It is guaranteed that the answer is the same for $d\pm10^{-4}$.