题目描述

There's an emergency—in space! You need to send your fleet's flagship as quickly as possible from star $0$ to star $N$, traveling through the other stars in increasing numerical order along the way ($0 \rightarrow 1 \rightarrow \ldots \rightarrow N$). Your flagship normally travels at a speed of $0.5$ parsecs per hour.

In addition to sending your flagship, you can order your engineers to build up to $L$ speed boosters at different stars. Building a speed booster takes $t$ hours, and all $L$ speed boosters can be built in parallel. While your flagship travels from a star with a completed speed booster to the next star, its speed is $1$ parsec per hour.

If a speed booster is completed at a star while your flagship is traveling from that star to the next one, your flagship will start moving faster as soon as the speed booster is completed.

How many hours does it take your flagship to get to star $N$ if you build speed boosters to make it arrive as soon as possible?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each contains integers, $L$, $t$, $N$ and $C$, followed by $C$ integers $a_i$, all separated by spaces. $a_i$ is the number of parsecs between star $k\times C+i$ and star $k\times C+i+1$, for all integer values of $k$.

For example, with $N=8$, $C=3$, $a_0=3$, $a_1=5$ and $a_2=4$, the distances between stars are $[3, 5, 4, 3, 5, 4, 3, 5]$.

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the case number (starting from $1$) and $y$ is a single integer: the number of hours it takes to reach star $N$. The answer is guaranteed to always be an integer.

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

Case #1: 54
Case #2: 20

提示

Explanation

In the second case, we can build one speed booster. The distances between stars are $[10, 4]$. We build the speed booster on the first star. After $4$ hours, our flagship has gone $2$ parsecs and the speed booster is complete. It takes our flagship another $8$ hours to get to star $1$, then $8$ more hours to get to star $2$, our destination.

Note: This problem takes place in a universe where the speed of light is much higher than $1$ parsec per hour, so we don't have to worry about special relativistic effects.

Limits

• $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$ is even.

Small dataset (12 Pts, Test set 1 - Visible)

• $1 \leq N \leq 1000$.
• $0 \leq L \leq 2$.
• Time limit: 30 3 seconds.

Large dataset (25 Pts, Test set 2 - Hidden)

• $1 \leq N \leq 10^6$.
• $0 \leq L \leq N$.
• Time limit: 60 6 seconds.