Weight of the System of Nested Segments solution codeforces
On the number line there arepoints, -th of which has integer coordinate and integer weight . The coordinates of all points are different, and the points are numbered from to .
A sequence of system of nested segments if for each pair ( ) the condition is satisfied. In other words, the second segment is strictly inside the first one, the third segment is strictly inside the second one, and so on.segments is called
For a given number, find a system of nested segments such that:
- both ends of each segment are one of given points;
- the sum of the weights minimal. of the points used as ends of the segments is
For example, let. The given points are marked in the picture, their weights are marked in red, their coordinates are marked in blue. Make a system of three nested segments:
- weight of the first segment:
- weight of the second segment:
- weight of the third segment:
- sum of the weights of all the segments in the system:
The first line of input data contains an integer( ) —the number of input test cases.
An empty line is written before each test case.
The first line of each test case contains two positive integers( ) and ( ).
The nextlines contain pairs of integers ( ) and ( ) — coordinate and weight of point number ( ) respectively. All are different.
It is guaranteed that the sum ofvalues over all test cases does not exceed .
Output Weight of the System of Nested Segments solution codeforces
For each test case, outputlines: in the first of them, output the weight of the composed system, and in the next lines output exactly two numbers — the numbers of the points which are the boundaries of the segment with the number ( ). The order in which you output the ends of the segment is not important — you can output the number of the left point first and then the number of the right point, or the other way around.
If there are several ways to make a system of nested segments with minimal weight, output any of them.
3 3 8 0 10 -2 1 4 10 11 20 7 -1 9 1 2 3 5 -2 3 6 -1 2 1 3 3 -1 2 4 4 0 8 2 2 5 5 -1 3 -2 1 0 -2 0 -5 -3
12 2 6 5 1 7 8 10 1 6 5 2 3 4 -6 5 1 4 2
The first test case coincides with the example from the condition. It can be shown that the weight of the composed system is minimal.
The second test case has onlypoints, so you need to use each of them to compose segments.