Gym - 101775C 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 S0 seconds from the house to first traffic light. Si seconds from traffic light i to traffic light i + 1 and SNseconds from Nth 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 Ai seconds green and then stays Bi seconds red and repeats. He also found that for all traffic lights, Ai + Bi are the same. He can modify the code to set different offsets OFFi for the traffic lights. Formally, Mr. Ang can set the offsets for the traffic lights to OFFi so that for each traffic light, Mr. Ang can go through it in time range [OFFi + k × (Ai + Bi), OFFi + k × (Ai + Bi) + Ai) and must wait in time range [OFFi + k × (Ai + Bi) + Ai, OFFi + (k + 1) × (Ai + Bi)) 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.

Input

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 S0, S1, ..., SN 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 Ai, Bi indicating the length of green light and red light of the ith traffic light.

• 1 ≤ T ≤ 50.
• 1 ≤ N ≤ 1000.
• 1 ≤ Ai, Bi ≤ 120. All Ai + Bi are the same.
• 1 ≤ Si ≤ 106.

Output

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 - 8of the correct answer.

Example

Input

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

Output

Case #1: 115.000000
Case #2: 135.000000

Note

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 OFF1 = 0, OFF2 = 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.

题意：给出两个红绿灯之间的时间以及每个红绿灯的红扥和绿灯时间，求最坏情况最小时间。

思路:当经过一个红灯的时候可以发现，可以通过调整OFF来保证接下来全是绿灯，所以答案就是最大的红灯时间和路程

#include<bits/stdc++.h>
using namespace std;
double sum;
int n;
int main()
{
    int t;
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d", &n);
        sum = 0;
        for(int i = 0; i <= n; ++i)
        {
            double x;
            scanf("%lf", &x);
            sum += x;
        }
        double tmp = 0;
        for(int i = 1; i <= n; ++i)
        {
            double a, b;
            scanf("%lf %lf", &a, &b);
            tmp = max(tmp, b);
        }
        sum += tmp;
        printf("Case #%d: %.10f\n", cas, sum);
    }
    return 0;
}