Skiing Competitions
A skier is preparing for a competition and has drawn a diagram of the ski slope to determine the best descent route. On this diagram, the gates on the slope are depicted as horizontal segments. No two gates overlap or share any points.
The skier's route should be a broken line that starts at the top of the mountain and ends at the base. Each subsequent vertex of this broken line must have a strictly lower y-coordinate than the previous one. An example of such a route is shown in the figure.
For every gate that the skier's route does not pass through, penalty points are incurred. The total penalty for the descent is the sum of the route's length and the penalty points for the gates not passed.
Your task is to write a program that calculates the minimum total penalty the skier can receive when completing the course.
Input
The first line of the input contains the number N - the number of gates on the course (0 ≤ N ≤ 500). The next two lines provide the coordinates of the start and finish points: S_x, S_y, F_x, F_y. Each of the following N lines contains four numbers: a_i, b_i, y_i, c_i - representing the x-coordinates of the left and right ends of the gate, the y-coordinate of the gate, and the penalty for not passing through that gate (a_i < b_i, F_y < y_i < S_y, c_i is an integer, 0 ≤ c_i ≤ 10000). All coordinates are integers and do not exceed 10000 in absolute value.
Output
Output the minimum possible total penalty for completing the course, with a precision of at least 4 decimal places.