一年前，Ang 先生加入了一家很棒的公司，并在公司所在的街道上租了一间房子。这家公司非常好，Ang 先生不需要打卡上下班。他可以睡个好觉，随时起床。

每天，他沿着街道步行，经过 $N$ 个编号为 $1, 2, 3, \dots, N$ 的交通灯，然后到达公司。从房子到第一个交通灯需要 $S_0$ 秒，从第 $i$ 个交通灯到第 $i+1$ 个交通灯需要 $S_i$ 秒，从第 $N$ 个交通灯到公司需要 $S_N$ 秒。前往公司的路上所花费的时间取决于交通灯的状态。

Ang 先生对交通灯产生了兴趣，并侵入了系统。在阅读代码后，他发现他路上的第 $i$ 个交通灯保持 $A_i$ 秒绿灯，然后保持 $B_i$ 秒红灯，如此循环。他还发现，对于所有交通灯，$A_i + B_i$ 的值都是相同的。他可以修改代码来为交通灯设置不同的偏移量 $OFF_i$。形式上，Ang 先生可以为交通灯设置偏移量 $OFF_i$，使得对于每个交通灯，他可以在时间范围 $[OFF_i + k \times (A_i + B_i), OFF_i + k \times (A_i + B_i) + A_i)$ 内通过，并且必须在时间范围 $[OFF_i + k \times (A_i + B_i) + A_i, OFF_i + (k + 1) \times (A_i + B_i))$ 内等待，其中 $k$ 为任意整数。

现在，Ang 先生希望在最坏情况下，使他从家到公司的通勤时间尽可能短。请找出这个最小时间（以秒为单位）。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个数字 $N$，表示交通灯的数量。 下一行包含 $N+1$ 个数字 $S_0, S_1, \dots, S_N$，表示题目描述中房子、交通灯和公司之间的步行时间（以秒为单位）。 随后有 $N$ 行，每行包含 2 个数字 $A_i, B_i$，表示第 $i$ 个交通灯绿灯和红灯的时长。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最坏情况下从家到公司的最小时间（以秒为单位）。 如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-8}$ 以内，则被视为正确。

数据范围

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $1 \le A_i, B_i \le 120$。所有 $A_i + B_i$ 的值相同。
• $1 \le S_i \le 10^6$

样例

输入 1

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

输出 1

Case #1: 115.000000
Case #2: 135.000000

说明

在第一个测试用例中，Ang 先生到达第一个交通灯需要 30 秒，在最坏情况下，他需要等待 15 秒直到绿灯亮起。然后花费 70 秒到达公司。总时间为 $30 + 15 + 70 = 115$ 秒。

在第二个测试用例中，Ang 先生到达第一个交通灯仍然需要 30 秒，因为 Ang 先生可以将 $OFF_1 = 0, OFF_2 = 25$。如果 Ang 先生在第一个交通灯遇到红灯，他肯定会在第二个交通灯遇到绿灯。因此在最坏情况下，Ang 先生花费 $30 + 20 + 15 + 0 + 70 = 135$ 秒。