Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bus Ride in Summer, Hot as Hell

By MosharrafOshy · Limits 1s, 512 MB

A bus goes from place A to B and returns from B to A. Now there are N stops in its route. INi people enter the bus and OUTi people went out from the bus in ith stop.

Your task is to find out the maximum number of stops ride by a person, excluding the stop where he/she got off from the bus. There is no specific ID for a person or someway to indicate who is in or who is out. Anyone can stay on the bus or leave. The followings are assumed to be true in this problem.

  • You can surely assume that always number of man in the bus ≥ 0.
  • At first people will get out from the bus, then other people will enter the bus.
  • After the last stop, total number of IN and OUT are equal.

Input

First line of input has an integer T (1 ≤ T ≤ 5) which denotes the number of test cases. Each case starts with a line containing one integer N (2 ≤ N ≤ 10). N is the stop number of the bus. Next N line contain two integers (0 ≤ INi and OUTi ≤ 50 for ith stop).

Output

At first print test case number just like sample output “Case X: ”, X is the test case number. Then print the maximum number of stops ride by a person.

Sample

InputOutput
2
2
1 0
0 1
4
2 0
2 2
3 0
0 5
Case 1: 1
Case 2: 2

Discussion

Statistics


82% Solution Ratio

tohidulEarliest, Jun '16

rrakibFastest, 0.0s

banglabidLightest, 0 B

habijabiShortest, 244B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.