Power Distribution

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After years of combing through the archive of the Ancients, Phoenix1369 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 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.

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 .

Original Problem Author: admin2; Problem Resource: Codechef