Sergeant Gica (this is a Romanian name) has just been announced that he is going to be sent out in the desert for training. He will have to walk L meters away from the army's headquarters, on a straight line. Since he is a bit lazy and because he has been allowed to pick up his own route, sergeant Gica takes a look at the map of the region. On the map, the army's headquarters are at the coordinates (0, 0). There are also N rectangular regions which have strictly positive coordinates marked on the map. Each rectangle has a given "delay coefficient". This means that the time needed to cross a line segment which is contained inside the rectangle, is equal to the
product between the length of the segment and the delay coefficient of the rectangle. The total time needed to travel all the L meters is equal to the sum of the times needed to travel every segment of the straight line which lies inside the zones marked on the map (including the desert).
Note that the desert (the space between the N rectangular zones) has its own delay coefficient.
The 1st line contains N (1 ≤ N ≤ 500), the number of rectangular zones marked on the map. The next N lines contain 5 numbers each: x1 y1 x2 y2 c. (x1, y1) are the coordinates of the lower left corner of the rectangle, (x2, y2) are the coordinates of the upper right corner of the rectangle and c is the delay coefficient of the rectangle. Then there is one more line which contains 2 numbers: c0 (the delay coefficient of the desert) and L (the number of meters sergeant Gica has to travel).
All numbers are positive integers not greater than 32000. L will be larger than the distance from (0, 0) (the headquarters) to any point located on the edges of the
rectangles (this means that the sergeant's "trip" will always end up in the desert and not inside any of the rectangular zones marked on the map).
On the 1st line, you should output the minimum time needed to travel L meters on a straight line, starting from (0, 0) and ending at a point with positive coordinates.
On the 2nd line you should output the coordinates of the point where sergeant Gica should go to (this point must be L meters away from (0, 0) and must have positive coordinates). If there are more solutions with the same minimum time, you may output any one of them.
You should output all 3 numbers with 6 decimal digits.
1 1 2 2 1
The sergeant walks a total of 1.414.. meters inside the rectangular zone and (3-1.414..) meters outside the zone (through the desert). Thus, the total time is: 1.414..
* 1 + (3 - 1.414..) * 2.
Автор задачи: Mugurel Ionut Andreica
Источник задачи: Romanian Open Contest, December 2001