Minimizing Maximum Speed for Timely Deliveries

A courier company must deliver n packages to n locations along a fixed route. The courier, Xiao K, must follow the specified order of stops and cannot skip any location. For each location, a time window [L, R] is given during which the package can be signed for. If Xiao K arrives before L, he must wait until L (the signing operation is instantaneous), but he must not start after time R.

Between consecutive stops, the distance is provided. Xiao K wants to minimize the maximum speed he has to use along the journey while still ensuring that every delivery is completed within its allowed time window. Your task is to determine the minimum possible value of the maximum speed that allows him to finish all deliveries on time.

Note: Assume that the courier starts at time 0 at the first location.

inputFormat

The input begins with an integer n (number of stops). Then follow n lines, each containing two numbers L_i and R_i (the earliest and latest time allowed for signing at stop i). Finally, there is a line with n-1 numbers representing the distances between consecutive stops.

It is guaranteed that a solution exists.

outputFormat

Output a single floating-point number: the minimum possible maximum speed required so that all parcels can be delivered on time. An absolute or relative error of 1e-6 is acceptable.

sample

3
0 10
2 15
6 20
4 4

0.4