우주 비상 사태 (작은 입력)

우주에서 비상 사태가 일어났다. 함대의 기함을 별 0에서 별 $N$까지 최대한 빨리 보내야 한다. 기함은 중간의 별을 번호가 커지는 순서대로 모두 거쳐 간다. 즉 0, 1, 2, 순서로 $N$까지 이동한다. 기함의 평소 속도는 시간당 0.5파섹이다.

기함을 보내는 것과 별개로, 서로 다른 별에 가속기를 최대 $L$개까지 세우라고 기술진에게 지시할 수 있다. 가속기 하나를 세우는 데 $t$시간이 걸리고, $L$개를 모두 동시에 세운다. 가속기가 완성된 별에서 다음 별로 이동하는 동안 기함의 속도는 시간당 1파섹이 된다.

기함이 어떤 별에서 다음 별로 이동하는 도중에 그 별의 가속기가 완성되면, 기함은 완성되는 순간부터 빨라진다.

기함이 별 $N$에 가장 빨리 닿도록 가속기를 세울 때, 도착까지 걸리는 시간은 몇 시간인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄이 주어진다. 각 줄에는 정수 $L$, $t$, $N$, $C$와 $C$개의 정수 $a_i$가 공백으로 구분되어 주어진다. $a_i$는 별 $k \times C + i$와 별 $k \times C + i + 1$ 사이의 거리이고, 단위는 파섹이며, 모든 정수 $k$에 대해 같은 값이 반복된다.

예를 들어 $N = 8$, $C = 3$, $a_0 = 3$, $a_1 = 5$, $a_2 = 4$이면 별 사이의 거리는 차례대로 [3, 5, 4, 3, 5, 4, 3, 5]이다.

제한

• $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$는 짝수이다
• $1 \le N \le 1000$
• $0 \le L \le 2$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 별 $N$에 닿기까지 걸리는 시간이다. 답은 항상 정수임이 보장된다.

$L = 1$, $t = 4$, $N = 2$이고 별 사이의 거리가 [10, 4]인 경우를 보자. 가속기를 별 0에 세운다. 4시간이 지나면 기함은 2파섹을 갔고 가속기가 완성된다. 남은 8파섹을 시간당 1파섹으로 8시간 만에 지나 별 1에 닿고, 별 1에는 가속기가 없으므로 4파섹을 다시 8시간에 지나 목적지인 별 2에 닿는다. 모두 합쳐 20시간이 걸린다.

이 문제의 우주에서 빛의 속도는 시간당 1파섹보다 훨씬 빠르므로 특수 상대성 효과는 생각하지 않아도 된다.