405069: GYM101775 C Traffic Light

One year ago, Mr. Ang joined a great company and he rented a house on the same street as the company. The company is so great that Mr. Ang doesn't need to punch in and out. He can have a good sleep and gets up at any time.

Every day, he walks along the street, goes through N traffic lights numbered 1, 2, 3, ..., N and arrives the company. It takes Mr. Ang S₀ seconds from the house to first traffic light. S_i seconds from traffic light i to traffic light i + 1 and S_N seconds from N^th traffic light to company. The time spent on the way to company depends on the state of traffic lights.

Mr. Ang got interested in the traffic lights and hacked into the system. After reading the code, he found that for traffic light i on his way, it stays A_i seconds green and then stays B_i seconds red and repeats. He also found that for all traffic lights, A_i + B_i are the same. He can modify the code to set different offsets OFF_i for the traffic lights. Formally, Mr. Ang can set the offsets for the traffic lights to OFF_i so that for each traffic light, Mr. Ang can go through it in time range [OFF_i + k × (A_i + B_i), OFF_i + k × (A_i + B_i) + A_i) and must wait in time range [OFF_i + k × (A_i + B_i) + A_i, OFF_i + (k + 1) × (A_i + B_i)) for all integers k.

Now Mr. Ang would like to make his commuting time from house to company as short as possible in the worst case. Find out the minimal time in second.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line which consists of one number N, indicating the number of traffic lights.

The next line consists of N + 1 numbers S₀, S₁, ..., S_N indicating the walking time between house, traffic lights and company in seconds as described in the problem.

Then followed by N lines each consists of 2 numbers A_i, B_i indicating the length of green light and red light of the i^th traffic light.

• 1 ≤ T ≤ 50.
• 1 ≤ N ≤ 1000.
• 1 ≤ A_i, B_i ≤ 120. All A_i + B_i are the same.
• 1 ≤ S_i ≤ 10⁶.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimal time in second from house to company in the worst case.

y will be considered correct if it is within an absolute or relative error of 10^- 8 of the correct answer.

2
1
30 70
15 15
2
30 15 70
10 20
20 10

Case #1: 115.000000
Case #2: 135.000000

In the first test case, it takes Mr. Ang 30 seconds to the first traffic light, in the worst case he had to wait 15 seconds until it gets green. Then 70 seconds to the company. Total time is 30 + 15 + 70 = 115 seconds;

In the second test case, it still takes Mr. Ang 30 seconds to the first traffic light, as Mr. Ang could make OFF₁ = 0, OFF₂ = 25. If Mr. Ang meets red light at the first traffic light, he will definitely meet green light at the seconds one. So in the worst case, it takes Mr. And 30 + 20 + 15 + 0 + 70 = 135 seconds.