Tuenti Challenge 8

Challenge 8 - Security by doorscurity

Hello agent your mission is to infiltrate a secure research facility

From some intel work, we know some security measures to keep intruders out. In this case the most dangerous ones is hallways filled with a corrosive gas that would fairly quickly penetrate any protection you might bring
The hallways are designed to keep people in it long enough for the gas to do its work.

Another operative has managed to get the specifications of the hallway.

  • Each hallway has a number of doors
  • Each door opens at a determined interval and remains open for one unit of time
  • It takes you one unit of time to cross the space between doors.
  • There is a panel at each end that shows the current state of the hallway.

In order to survive the hallway with your equipment, you need to find a moment when you can get down it in one go without stopping.

Input

The first line has an integer C, which is the number of cases for the problem.
Each case starts with a line with an integer D, which is the number of doors in the hallway.
D lines follow, two integers P and T, indicating that the door opens every P units of time and that T units of time have passed since the last time it opened, relative to the time you get to the hallway (e.g. P = 10, T = 6 means the door will open at 4(10-6) and then every 10 units of time).

Output

For each case, there should be a line starting with "Case #x: " followed by the earliest moment in time (relative to your arrival at the hallway panel) when you can go the hallway in one go without stopping, but if that never happens, output NEVER. Every line is followed by a new line character.

Examples

Case 1:

2
7 2
9 3


            
Case 2:

3
5 2
9 3
7 2

            
Case 3:

4
7 2
23 20
21 20
27 3
            
Case 4:

4
59 23
65 25
34 15
9 3
            

In Case 1 the answer is 5, 5 units of time after you arrival you start running, the first door should be open, and the second door opens at 6, just as you are crossing the space between the doors
In Case 2 the answer is 248, you cross door 1 at 248, door 2 at 249 and door 3 at 250
In Case 3 the answer is NEVER
In Case 4 the answer is 711399, you cross door 1 at 711399, door 2 at 711400, door 3 at 711401 and door 4 at 711402

Limits

  • 2 ≤ D ≤ 100
  • 1 ≤ P ≤ 10 000 000
  • 0 ≤ TP

Sample Input

6
2
7 3
8 6
2
13 9
11 7
3
22 21
29 4
3 1
4
7 2
23 20
21 12
27 3
5
12 2
31 21
41 39
25 19
47 31
6
37 17
51 31
11 7
53 40
28 23
47 37

Sample Output

Case #1: 25
Case #2: 69
Case #3: 111
Case #4: NEVER
Case #5: 7669378
Case #6: 261595237

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.