Space Emergency (Large)

There is an emergency in space. You have to send your fleet's flagship from star $0$ to star $N$ as quickly as possible, passing through the stars in increasing order along the way ($0 \to 1 \to \dots \to N$). The flagship normally travels at $0.5$ parsecs per hour.

Apart from sending the flagship, you can order your engineers to build up to $L$ speed boosters, each on a different star. Building one booster takes $t$ hours, and all $L$ of them start at time $0$, so every booster is finished at time $t$. 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 on a star is finished while the flagship is traveling from that star to the next one, the flagship speeds up the moment the booster is finished.

You build the boosters so that the flagship arrives as early as possible. How many hours does it take the flagship to reach star $N$?

The first line contains the number of test cases $T$. Each of the next $T$ lines contains the integers $L$, $t$, $N$, $C$, followed by $C$ integers $a_0, \dots, a_{C-1}$, all separated by spaces. For every integer $k$, $a_i$ is the distance in parsecs between star $k \times C + i$ and star $k \times C + i + 1$.

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]$.

Constraints

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

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 always an integer.

In the second test case of the first sample you can build one booster, and the distances between consecutive stars are $[10, 4]$. Build the booster on star $0$. After $4$ hours the flagship has covered $2$ parsecs and the booster is finished. The remaining $8$ parsecs take $8$ more hours, so the flagship reaches star $1$ at hour $12$, and $8$ more hours bring it to star $2$, the destination.

In the universe of this problem the speed of light is much higher than $1$ parsec per hour, so special relativistic effects do not matter.