Space Emergency (Small)

There is an emergency in space. You have to send your fleet's flagship from star 0 to star $N$ as fast as you can, and it passes through every star in between in increasing order of number: 0, then 1, then 2, and so on up to $N$. The flagship normally travels at 0.5 parsecs per hour.

Separately from sending the flagship, you can order your engineers to build up to $L$ speed boosters at distinct stars. One booster takes $t$ hours to build, and all $L$ of them are built at the same time. While the flagship travels from a star with a finished booster to the next star, its speed is 1 parsec per hour.

If the booster at a star finishes while the flagship is already on its way from that star to the next one, the flagship speeds up the moment the booster finishes.

If you place the boosters so that the flagship reaches star $N$ as early as possible, how many hours does the trip take?

The first line contains the number of test cases $T$. Each of the next $T$ lines contains the integers $L$, $t$, $N$ and $C$, followed by $C$ integers $a_i$, all separated by spaces. $a_i$ is the distance in parsecs between star $k \times C + i$ and star $k \times C + i + 1$, and the same value repeats for every integer $k$.

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

Limits

• $1 \le T \le 100$
• $1 \le C \le 1000$
• $C \le N$
• $1 \le a_i \le 10^4$
• $0 \le t \le 10^{11}$
• $t$ is even
• $1 \le N \le 1000$
• $0 \le L \le 2$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of hours it takes to reach star $N$. The answer is guaranteed to be an integer.

Take the case $L = 1$, $t = 4$, $N = 2$ with distances [10, 4]. Build the booster at star 0. After 4 hours the flagship has covered 2 parsecs and the booster is finished. It covers the remaining 8 parsecs at 1 parsec per hour, so it reaches star 1 eight hours later, and since star 1 has no booster it spends another 8 hours on the 4 parsecs to star 2, the destination. The trip takes 20 hours in total.

This problem takes place in a universe where the speed of light is far above 1 parsec per hour, so you do not have to worry about special relativistic effects.