Traffic Light Gym - 101775C

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 SN seconds 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 - 8 of 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.

思维题：

我们可以完全按照  同一排列来做，当时没能想出来合适的表达方式，不知道怎样来表示两个红绿灯的时间关系。发现，其实只要把他们都左端点对齐 放好就行了，假设两个点的差值就是 上下的对应位置，挺好的思维题。

 

真的差一点，never give  up!

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)

const int N=1100;
const double eps=1e-9;
double A[N],B[N],S[N];

int n;
int main(){
    int T;
    scanf("%d",&T);
    rep(kase,0,T){
        scanf("%d",&n);
        double ans=0;
        rep(i,0,n+1){
            scanf("%lf",&S[i]);
            ans+=S[i];
        }
        double tmp=0;
        rep(i,0,n){
        	scanf("%lf %lf",&A[i],&B[i]);
			tmp=max(tmp,B[i]);
        }
        printf("Case #%d: %.10f\n",kase+1,ans+tmp);
    }
    return 0;
}