Problem C
Alchemy

Since the days of yore, alchemy has been studied and practiced. The practice makes alchemists able to transmute materials into other forms. Transmuting materials requires drawing a transmutation circle on the ground. A little known fact about transmutation circles is they can be drawn inside or outside other transmutation circles. By activating certain configurations in the correct order, more powerful transmutations can be produced. Activating circles incorrectly can have drastic effects on the alchemist’s body.

A young alchemist named Nicholas Flamel would like to learn the ways of alchemy. He is going to draw several configurations of transmutation circles on the ground. When a circle is drawn it burns bright red representing the element of fire. The drawing of the circle itself produces no energy, but it has an effect on any and all circles that are already drawn inside! All of the circles inside the newly drawn circle quickly change to their complement elements. Fire changes to a cool blue representing water. Circles that were blue for water will burn fiery red once again. This transformation can either create or drain energy. Interestingly, it is the transformation, and not the drawing, that emanates energy. Beware, energy can go negative at any time draining the alchemist’s life force.

Nicholas wants to get as much out of his transmutations as possible. To do so requires him to draw his circles in an order that releases the most energy. Determine the maximum amount of energy that can be released, and the order in which he should draw the circles.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will start with a line with a single integer $n$ ($1 \le n \le 2\, 000$) indicating the number of circles. The next $n$ lines will describe the circles, in order, from circle $1$ to circle $n$. Each line will describe its circle with $5$ integers, with a single space between integers:

x y r a b

Where $(x,y)$ is the center of the circle ($-20\, 000 \le x,y \le 20\, 000$), $r$ is the radius of the circle ($1 \le r \le 20\, 000$), $a$ is the energy released in the transition from fire to water, and $b$ is the energy released in the transition from water to fire ($-500 \le a,b \le 500$). It is guaranteed that no two circles’ edges will intersect.

Output

Output exactly two lines. On the first line output a single integer representing the maximum energy that can be produced by activating the circles. On the second line output the order of drawing the circles that can produce that energy. If more than one order will work, output the one that comes first lexicographically.

8
0 0 100 -100 -100
0 0 50 -10 -10
0 0 10 -100 500
0 0 1 100 100
1000 1000 100 -1 1
1000 1000 50 -1 1
1000 1000 10 -1 1
1000 1000 1 -1 1

700
4 3 1 2 5 6 7 8