After years of combing through the archive of the Ancients,
has finally found an interesting problem for the Don Mills Programming Club:Given the x-coordinates of houses arranged in a row, some of which can generate their own power, output the minimum length of electrical wire required to connect every home to a source of power, either directly or indirectly.
Input Specification
The first line of the input contains an integer denoting the number of test cases.
The first line of a case contains an integer , denoting the number of homes arranged in a line.
The next lines of a case each contain space-separated integers: and denoting the x-coordinate of the house, and whether it generates its own power, respectively.
Output Specification
Output lines, each containing a single integer on a line by itself, the of which represents the minimum length of wire needed to supply power to all houses for the case.
Constraints
It is guaranteed that at least one home will be able to generate its own electricity.
Subtask 1 [30%]
Subtask 2 [70%]
Sample Input
2
3
1 1
2 0
5 0
3
1 1
8 0
9 1
Sample Output
4
1
Explanation
In the first case, wires can be added between houses # and # and houses # and # for a total length of . House # gets power because it is indirectly connected to house # (via house #).
In the second case, house # is the only house which requires power. Since it is closer to house #, the length of the wire required is .
Comments