Irvanistan and Jikjikestan are two neighboring countries that have fought several wars with many casualties over their
border dispute. Despite the loss of lives in the scale of tens of thousands, none of their border claims have been accepted by the other party.

Recently, the logical leaders who have gained control of both countries have accepted the United Nations proposal to resolve their border dispute. The proposal is to come up with a shorter and simplified version of the border that is
calculated by a fair computer program.

To describe the problem accurately, let the current border P be a set of non-crossing line segments each connecting two border points. Let p₁, p₂, ..., p_N be these border points; i.e., P is exactly composed of the line segments connecting p_i and p_i+1, for 1 <= i < N.

The UN suggests to create a new border C with points c₁, c₂, ..., c_K, in such a way that c₁ = p₁ and c_K = p_N and the
following constraints are satisfied.

1. Each point c_i should be one of the points p₁, p₂, ..., p_N. Obviously, if c_i = p_r and c_i+1 = p_s, then s > r.


2. Each point p_i should have a distance of at most some given number D from C. The distance of p_i from C is defined as the distance from p_i to the closest point on C. Note that, the line segment drawn from p_i to the closest point on C, is always perpendicular to C.

Your task is to find a new border C with the shortest possible length, while adhering to the above constraints.