Description

太空中发生了紧急情况！你需要尽快将你的舰队旗舰从恒星 $0$ 送到恒星 $N$，途中必须按编号递增顺序依次经过所有恒星（$0 \rightarrow 1 \rightarrow \ldots \rightarrow N$）。你的旗舰通常以 $0.5$ 秒差距每小时的速度航行。

除了派出旗舰外，你还可以命令工程师在不同的恒星上建造最多 $L$ 个加速器。建造一个加速器需要 $t$ 小时，所有 $L$ 个加速器可以并行建造。当你的旗舰从一个已完成加速器的恒星出发前往下一个恒星时，它的速度将提升为 $1$ 秒差距每小时。

如果旗舰在从某个恒星前往下一个恒星的途中，该恒星上的加速器建造完成，那么旗舰会在加速器完成的瞬间开始以更快的速度前进。

如果你合理建造加速器，使旗舰尽快到达恒星 $N$，那么旗舰需要多少小时才能到达？

Input Format

输入的第一行为测试用例数 $T$。接下来的 $T$ 行，每行包含整数 $L$、$t$、$N$ 和 $C$，后跟 $C$ 个整数 $a_i$，所有数值以空格分隔。$a_i$ 表示对于所有整数 $k$，从恒星 $k\times C+i$ 到恒星 $k\times C+i+1$ 之间的距离（单位为秒差距）。

例如，若 $N=8$，$C=3$，$a_0=3$，$a_1=5$，$a_2=4$，则各段距离为 $[3, 5, 4, 3, 5, 4, 3, 5]$。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是旗舰到达恒星 $N$ 所需的总小时数。保证答案总是整数。

2
2 20 8 2 3 5
1 4 2 2 10 4

Case #1: 54
Case #2: 20

Hint

说明

在第二个测试用例中，我们可以建造一个加速器。两段距离分别为 $[10, 4]$。我们在第一个恒星建造加速器。经过 $4$ 小时，旗舰已前进 $2$ 秒差距，此时加速器建造完成。旗舰再用 $8$ 小时到达恒星 $1$，然后再用 $8$ 小时到达目的地恒星 $2$。

注意：本题设定的宇宙中，光速远大于 $1$ 秒差距每小时，因此无需考虑相对论效应。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq C \leq 1000$。
• $C \leq N$。
• $1 \leq a_i \leq 10^4$。
• $0 \leq t \leq 10^{11}$。
• $t$ 为偶数。

小数据范围（12 分，测试集 1 - 可见）

• $1 \leq N \leq 1000$。
• $0 \leq L \leq 2$。
• 时间限制：3 秒。

大数据范围（25 分，测试集 2 - 隐藏）

• $1 \leq N \leq 10^6$。
• $0 \leq L \leq N$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译