Berland is in civil war. This time peaceful solution is hardly possible. Collapse to the East and West Berland is inevitable! Commander-in-chief of grey, general Kruglyakovski, has made a decision to hasten the process and to surround his headquarters with a wall (which later be called Great Berland Wall). The wall should be built in such a way that the enemy's headquarters would stay at the other side of the wall.

Looking to the Berland map general Kruglyakovski noticed that the country consists of a number of provinces. Each province has the form of a simple (but possibly not convex) polygon. The country of Berland has no enclaves and does not contain any enclaves of other countries inside, i.e. it is possible to get from one point of Berland to another without leaving the country. The "passability" is known for each segment of the border of each province. "Passability" is the maximum speed the soldier can move with along the corresponding segment.

General Kruglyakovski decided that the wall will pass only along the borders of the provinces and will have the form of a simple polygon. He sent the group of soldiers to build the wall during the night. And you got a task to find such a form and position of the wall that the time of building would be minimal. The time of building of the section of the wall is equal to the "passability" of the corresponding border segment. The time of building of the wall is equal to the sum of building of its segments.

The first line of the input file contains the number of segments of province borders — integer number N (5≤ N≤ 300). The segments themselves follow further. Each segment is defined by five numbers x₁, y₁, x₂, y₂, v, where (x₁, y₁) and (x₂, y₂) are the coordinates of the segment end points and the integer number v (1 ≤ v ≤ 1000) is the "passability". Any pair of segments has not more than one common point and this point can only be their common end-point. Input data finishes with one more quadruple of numbers X₁, Y₁, X₂, Y₂, where (X₁, Y₁), (X₂, Y₂) are the coordinates of headquarters of the general Kruglyakovski and his opponent correspondingly. Both headquarters are situated strictly inside one of the provinces. The headquarters are situated in different provinces. All coordinates in the input are integer numbers less than 10⁴ by the absolute value.

Write to the first line of the output the total time of building of the wall. Write to the second line the number of border segments the wall will occupy. To the next line write the sequence of the numbers of the segments. The segments are numbered in the order they appear in the input. If there are several solutions choose any of them.

sample input	sample output
13 0 6 3 6 9 0 0 4 2 8 4 4 6 6 7 2 4 3 6 1 3 6 6 6 1 6 4 6 6 1 4 2 6 4 1 0 0 0 6 6 2 2 2 4 1 2 2 4 2 1 0 6 2 4 5 2 4 4 4 4 4 2 4 4 3 3 3 2 5	6 6 9 10 4 7 5 6