Trapezoid Walkway

Interview

Time limit2sMemory limit256 MB

Summary

Find the cheapest chain of trapezoid stones joining two given widths, where each stone links its two edge lengths at a cost tied to its area.

Level: Medium4 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

You are putting a prefabricated gazebo in your back yard and connecting it to the back porch with a paved walkway. Every paving stone sold at the local home improvement store has the shape of an isosceles trapezoid, the shape left over when you cut a corner off an isosceles triangle along a line parallel to the base. Three numbers describe one stone: the length $a$ of one parallel edge, the length $b$ of the other parallel edge, and the perpendicular distance $h$ between those two edges.

You build the walkway by joining stones along their parallel edges. A parallel edge of the first stone meets the back porch, and a parallel edge of the last stone meets the gazebo. Two stones may be joined only when the two edges that meet have exactly the same length. A stone may touch the back porch or the gazebo only when the edge that touches it has exactly the same length as the porch or the gazebo. If the porch and the gazebo have the same width, the walkway may be empty, and then it costs nothing.

A paving stone costs 2 cents per square centimeter of area. The yard is large, so the length of the walkway does not matter. Find the cheapest walkway.

Input

The input holds several test cases. Each test case begins with a positive integer $n$ ( $1 \le n \le 1000$ ), the number of stone types on sale. Each of the next $n$ lines holds three positive integers $a$ , $b$ and $h$ ( $1 \le a, b, h \le 1000$ ), measured in centimeters, describing one type. No two types are identical, and the store keeps an unlimited stock of every type, so you may buy as many stones of each type as you need. The last line of the test case holds two positive integers not greater than 1000: the width of the back porch where the walkway starts, then the width of the gazebo edge where the walkway ends. A line holding 0 in place of $n$ ends the input. Every test case admits at least one walkway.

Output

For each test case, print one line with the cost of the cheapest walkway in dollars, written with exactly two digits after the decimal point.

Examples2

Example 1

Input

6
120 350 60
120 150 95
240 300 60
240 350 220
150 300 100
300 350 120
120 240
2
100 140 50
100 140 80
140 100
2
150 250 100
150 250 60
150 150
0

Expected output

1030.50
120.00
0.00

Example 2
Input
```
1
1 2 1
1 2
0
```
Expected output
```
0.03
```