Traffic Light （CFGym 101775C ）

Description

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.

 

Input

INPUT
2
1
30 70
15 15
2
30 15 70
10 20
20 10
OUTPUT
Case #1: 115.000000
Case #2: 135.000000

 

Hint

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.

题意：T组数据，n个红绿灯，下一行n+1个数，前n个表示到第i个红绿灯需要的时间，第n+1个数表示走完红灯之后到公司的时间，接下来n行表示第i个红绿灯绿灯和红灯停留的时间，问最坏情况下到公司需要的最少时间。

思路：最坏的情况还有最少时间？最坏情况就是等的红灯时间最长，最少时间是就等一个红灯，找一个红灯最长的时间再加上所有路程花费的时间就AC了。

/***
 * ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │N L│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│    │Alt │         Space         │ Alt│    │    │Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
#define PI acos(-1)
const int mod=1e9+7;
const int M=1e5 + 10;
typedef long long ll;
int main()
{
    int T,n,m,i,j,kk,a,b;
    scanf("%d",&T);
    for(kk=1;kk<=T;kk++)
    {
        ll ans=0;
        scanf("%d",&n);
        for(i=1;i<=n+1;i++)
        {
            scanf("%d",&a);
            ans+=a;
        }
        int maxx=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            if(b>=maxx)
                maxx=b;
        }
        printf("Case #%d: %lld.000000\n",kk,ans+maxx);
    }
    return 0;
}