Kirill decided to go skydiving. He arrived at a Cartesian coordinate system, in which ground and air are separated by the line y = 0 m, the air is above (in the half-plane y ≥ 0 m), the ground is below. Gravity is directed downwards (in the direction of decrease of coordinate y).
Kirill ascended to the point (x, y) and started falling. He is falling with gravitational acceleration equal to 10 m/s2. Kirill’s starting vertical speed is equal to 0 m/s. But his horizontal speed is fully in his control: at any point in time Kirill can change his horizontal speed to any value between −1 m/s and 1 m/s.
Kirill wants to spend as much time in the air as possible. Luckily for him, there are n clouds in the air. Kirill calculated that i-th cloud is located in the point (xi, yi) and has density ci. If Kirill reaches a point where the i-th cloud is located, he will instantly stop and spend the next ci seconds motionless in that point. After that he will start falling again, starting with a vertical speed of 0 m/s, and will be able to change his horizontal speed again to any value between −1 m/s and 1 m/s.
Find out the longest possible time Kirill could spend falling. He stops falling when he reaches the line y = 0 m.
The first line contains one integer n — amount of clouds (0 ≤ n ≤ 50000).
The second line contains two integers x and y — Kirill’s starting coordinates in meters (−10000 ≤ x ≤ 10000; 1 ≤ y ≤ 10000).
Then n lines follow, i-th of them contains three integers xi, yi and ci — coordinates of a cloud and its density (−10000 ≤ xi ≤ 10000; 0 < yi < y; 1 ≤ ci ≤ 10000). It is guaranteed that all clouds are located in distinct points.
Output one number — the maximum possible duration of falling in seconds. Your answer is considered correct if its absolute or relative error doesn’t exceed 10−4.
-1 30 2
-1 60 1
0 40 10
1 20 1
1 50 1
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020