Problem G
Trapezoid Walkway

You are planning to place a small, prefabricated gazebo in your back yard, with a paved walkway connecting it to your back porch. You’ll build the walkway out of paving stones purchased at your local home improvement store. The paving stones come in a variety of sizes, but they are all shaped like isosceles trapezoids. As illustrated on the left of Figure 1, an isosceles trapezoid is what you get if you take an isosceles triangle and cut off a corner with a line that is parallel to the base. We can describe such a paving stone with three parameters: the length of one of its parallel edges, $a$, the length of the other parallel edge, $b$, and the perpendicular distance, $h$, between these edges.

Figure 1: Isosceles trapezoid shape (left), walkway example (center) and join requirements (right)

You’re going to build your walkway by joining the parallel edges of the paving stones, with one parallel edge meeting the back porch at the start and another meeting the gazebo at the end. You want your walkway to look nice, so you won’t permit any of the situations illustrated on the right of Figure 1. Where two paving stones meet, their edges must be exactly the same length. Likewise, where a paving stone meets the back porch or the gazebo, its edge must be exactly the same length. Fortunately, your home improvement store has a wide selection of different trapezoid-shaped paving stones, so you are confident you can build a walkway that satisfies these requirements.

Paving stones are priced at two cents per square centimeter of surface area. You have a big back yard, so you don’t care how long your walkway is. You just want the one that’s the least expensive.

Input

Input will consist of multiple test cases. Each test case will start with a positive integer, $n$, the number of different types of paving stones available. The value, $n$, will be at least 1 and no greater than 1000. The next $n$ lines each describe a type of stone by giving the lengths of its sides, $a$, $b$ then $h$. These three values will be positive integers, measured in centimeters and not greater than 1000. No two types of stones are identical, but your home improvement store has a large stock of paving stones, so you can buy as many of each type as you need. The last line of each test case gives the width of the back porch, where the walkway will start, followed by the width of the edge of the gazebo where the walkway will end. A value of zero for $n$ will mark the end of all test cases.

Output

For each test case, print the total cost, in dollars, for the least expensive walkway that meets your requirements. It will always be possible to build such a walkway.

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

1030.50
120.00
0.00