F. Escaping the Sun
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

During his vacation in Aracaju, Samuell decided to spend the morning swimming at Atalaia Beach, one of the city's postcards, famous for its beautiful and long stretch of sand.

When it was time to leave, a problem came up: with the sun high in the sky, he must cross the entire beach, from the sea to the boardwalk, and request an Uber. To avoid getting sunburned, Samuell plans to use the shadows of the beach umbrellas spread across the sand and choose a route that minimizes the distance walked under the sun.

Formally, the beach can be represented by the strip between two parallel lines: one is the line where the sea meets the sand ($$$y = 0$$$), and the other is the boardwalk ($$$y = H$$$), at distance $$$H$$$ from the first one. There are $$$N$$$ beach umbrellas; the $$$i$$$-th one casts a circular shadow with center $$$(x_i, y_i)$$$ and radius $$$r_i$$$.

Assume Samuell can swim freely underwater without being exposed to the sun, and can leave the water at any point on the sea line. Once on the sand, he can:

  • walk under the shadow of a beach umbrella, including moving directly to another one when their shadows touch or overlap;
  • leave the sand at any point on the boardwalk.

Help Samuell determine the minimum distance he must walk under the sun to reach the boardwalk.

Input

The first line contains two integers $$$N$$$ and $$$H$$$ ($$$0 \leq N \leq 1000$$$, $$$1 \leq H \leq 10^{5}$$$), respectively the number of beach umbrellas and the distance between the sea line and the boardwalk.

Each of the next $$$N$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, and $$$r_i$$$ ($$$0 \leq x_i \leq 10^5$$$, $$$0 \leq y_i \leq H$$$, $$$1 \leq r_i \leq 10^{5}$$$), the center and radius of the $$$i$$$-th beach umbrella. A beach umbrella's shadow may extend beyond the sea line or the boardwalk.

Output

Print a single real number: the minimum distance under the sun that Samuell must walk to cross the sand, from the sea to the boardwalk.

Your answer will be considered correct if its absolute or relative error with respect to the expected answer is at most $$$10^{-6}$$$.

Examples
Input
2 10
2 2 2
5 8 2
Output
2.7082039325
Input
2 10
5 3 2
5 7 2
Output
2.0000000000
Input
1 6
3 3 5
Output
0.0000000000
Note

Explanation for example 1

In the first example, Samuell can take a route where he walks $$$3\sqrt{5} - 4$$$ under the sun.

Explanation for example 2

In the second example, Samuell walks one unit under the sun to reach the first shadow. The two shadows touch, allowing him to move from one to the other without being exposed. Then he walks one more unit to the boardwalk. Therefore, the total distance under the sun is $$$1 + 1 = 2$$$.

Explanation for example 3

In the third example, the only shadow has radius $$$5$$$ and center $$$(3, 3)$$$. Since it reaches both the sea line and the boardwalk, Samuell can cross the whole beach while staying in the shadow. Therefore, the distance walked under the sun is $$$0$$$.