Optimal Track Selection

In this problem, you are given multiple test cases. Each test case consists of multiple runners. Each runner provides a list of preferred tracks along with their expected finish times. The first number in each runner's line indicates the number of (track, time) pairs that follow. Your task is to sum the finish times for each track within a test case and then determine the track with the smallest total finish time. In the case of a tie, choose the track with the smallest numerical track ID.

Let ( T ) be the number of test cases. For each test case, let ( n ) be the number of runners, and each runner's input is given in the format: [ k\ a_1\ t_1\ a_2\ t_2\ \ldots\ a_k\ t_k ] where ( k ) is the number of track-time pairs. Compute the sum of finish times for each track and output the result in the format "Case #X: Y", where ( X ) is the test case number (starting from 1) and ( Y ) is the optimal track ID.

inputFormat

Input is read from standard input (stdin). The first line contains an integer ( T ) indicating the number of test cases. For each test case, the first line contains the integer ( n ) representing the number of runners. Each of the following ( n ) lines contains a series of space-separated integers. The first integer in each line is ( k ), the number of (track, finish time) pairs, followed by ( 2k ) integers representing the track ID and expected finish time.

outputFormat

For each test case, output a single line in standard output (stdout) in the format "Case #X: Y", where ( X ) is the test case number (starting from 1) and ( Y ) is the track ID that has the lowest total finish time across all runners. If there is a tie, the track with the smallest track ID is chosen.## sample

2
3
2 1 20 3 50
1 2 30
2 1 15 2 25
2
1 1 50
1 2 40

Case #1: 1
Case #2: 2