우주 비상사태 (라지)

우주에서 비상사태가 벌어졌다. 함대의 기함을 $0$번 별에서 $N$번 별까지 최대한 빨리 보내야 한다. 기함은 번호가 커지는 순서대로 $0 \to 1 \to \dots \to N$을 차례로 지나간다. 기함의 평소 속도는 시속 $0.5$파섹이다.

기함을 출발시키는 것과 별개로, 엔지니어에게 서로 다른 별에 가속 장치를 최대 $L$개까지 지으라고 지시할 수 있다. 가속 장치 하나를 짓는 데 $t$시간이 걸리고 $L$개를 모두 $0$시각에 동시에 짓기 시작하므로, 모든 가속 장치는 $t$시각에 완성된다. 완성된 가속 장치가 있는 별에서 다음 별로 가는 동안 기함의 속도는 시속 $1$파섹이 된다.

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

가장 이른 시각에 도착하도록 가속 장치를 지었을 때, 기함이 $N$번 별에 닿기까지 걸리는 시간은 몇 시간인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄이 주어진다. 각 줄에는 정수 $L$, $t$, $N$, $C$와 $C$개의 정수 $a_0, \dots, a_{C-1}$이 공백으로 구분되어 주어진다. $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]$이다.

제한

• $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}$이고, $t$는 짝수이다
• $0 \le L \le N$

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

첫 번째 예제의 두 번째 테스트 케이스에서는 가속 장치를 하나 지을 수 있고, 이웃한 별 사이의 거리는 $[10, 4]$이다. $0$번 별에 가속 장치를 짓자. $4$시간이 지나면 기함은 $2$파섹을 이동했고 가속 장치가 완성된다. 남은 $8$파섹을 가는 데 $8$시간이 더 걸려 $12$시각에 $1$번 별에 닿고, 다시 $8$시간이 걸려 목적지인 $2$번 별에 닿는다.

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