题目描述

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} \to p_{2} \to$ . . . $\to 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}} \to p_{i_{2}} \to · · · \to p_{i_{m}},$ where $1 = i_{1} < i_{2} < · · · < 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}} \to p_{i_{k+1}}$ exceeds $d$ , for such $k$ , that $i_{k} < j < i_{k+1}.$

Original route

New route

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 ± 10^{−4}.$

5 2
2 6
8 2
14 2
12 9
13 8

3

提示

Time limit: 2 s, Memory limit: 256 MB.