Description

Xiao K successfully cracked the ciphertext. But when taking a bus to country X, he found his wallet had been stolen, so he had no choice but to work as a courier to save enough fare to go pay respect to the "Orz Jiaozhu".

A courier company needs to deliver $n$ packages to $n$ locations and assigns Xiao K a predetermined route. Xiao K must drive and deliver according to the order of locations given by the route, and he cannot skip any location. Xiao K is given the receivable time window for each location and also knows the distance from each location to the next along the route. If he arrives at a location earlier than its time window, he must wait there until the window opens, but he cannot be later than the end of the time window. The signing process is considered instantaneous.

To save fuel, Xiao K wants the car’s maximum speed to be as small as possible while completing all deliveries. Please design a plan for him and compute the minimal possible maximum speed.

Input Format

The first line contains a positive integer $n$, the number of locations to deliver to.

The next $n$ lines: on the $(i+1)$-th line there are 3 positive integers $x _ i, y _ i, s _ i$, meaning that, in the route order, the time window to sign for the $i$-th location is $[x _ i, y _ i]$ (earliest at time $x _ i$ from the departure moment, latest at time $y _ i$ from the departure moment), the distance from the previous location to the $i$-th location is $s _ i$, and it is guaranteed that $x _ i$ are increasing along the route.

Assume $s _ 1$ is the distance from the starting point to the first location, and the departure time is $0$.

Output Format

Output a single positive number: the minimal possible maximum speed of the car, rounded to two decimal places.

3
1 2 2
6 6 2
7 8 4

2.00

Hint

Constraints

• For 20% of the testdata, $0 < n \le 10$.
• For 30% of the testdata, $0 < x_i, y_i, s_i \le 1000$.
• For 50% of the testdata, $0 < n \le 1000$.
• For 100% of the testdata, $0 < n \le 2\times 10^5$, $x_i \le y_i \le 10^8$, $s_i \le 10^7$.

Sample Explanation On the first leg, use speed $1$ to arrive at time $2$ at the first location. On the second leg, use speed $0.5$ to arrive at time $6$ at the second location. On the third leg, use speed $2$ to arrive at time $8$ at the third location.

Translated by ChatGPT 5