우주 비상사태

우주에서 비상사태가 발생했다! 함대의 기함을 별 0에서 별 N까지 최대한 빨리 보내야 하며, 도중에 있는 다른 별들을 번호가 증가하는 순서대로 거쳐야 한다(0→1→...→N). 기함은 평소 시간당 0.5파섹의 속도로 이동한다.

기함을 보내는 것에 더해, 기술자들에게 서로 다른 별에 최대 L개의 속도 증폭기를 건설하도록 명령할 수 있다. 속도 증폭기를 건설하는 데에는 t시간이 걸리며, L개의 속도 증폭기는 모두 병렬로 건설할 수 있다. 기함이 완성된 속도 증폭기가 있는 별에서 다음 별로 이동하는 동안에는 속도가 시간당 1파섹이다.

기함이 어떤 별에서 다음 별로 이동하는 도중에 그 별의 속도 증폭기가 완성되면, 속도 증폭기가 완성되는 즉시 기함은 더 빠르게 이동하기 시작한다.

기함이 최대한 빨리 도착하도록 속도 증폭기를 건설할 때, 기함이 별 N에 도착하는 데 몇 시간이 걸리는가?

제한

1 ≤ T ≤ 100. 1 ≤ C ≤ 1000. C ≤ N. 1 ≤ $a_{i}$ ≤ $10^{4}$. 0 ≤ t ≤ $10^{11}$. t는 짝수이다. 메모리 제한: 1GB.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 1000. 0 ≤ L ≤ 2. 시간 제한: 30초.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{6}$. 0 ≤ L ≤ N. 시간 제한: 60초.

입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 정수 L, t, N, C가 주어진 뒤 C개의 정수 $a_{i}$가 주어지며, 모두 공백으로 구분된다. 모든 정수 k에 대해 $a_{i}$는 별 kC+i과 별 kC+i+1 사이의 거리를 파섹 단위로 나타낸다.

예를 들어 N=8, C=3, $a_{0}$=3, $a_{1}$=5, $a_{2}$=4이면 별들 사이의 거리는 $[3, 5, 4, 3, 5, 4, 3, 5]$이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 별 N에 도달하는 데 걸리는 시간을 나타내는 하나의 정수이다. 답은 항상 정수임이 보장된다.

설명

두 번째 케이스에서는 속도 증폭기를 하나 건설할 수 있다. 별들 사이의 거리는 $[10, 4]$이다. 첫 번째 별에 속도 증폭기를 건설한다. 4시간이 지나면 기함은 2파섹을 이동했고 속도 증폭기가 완성된다. 기함이 별 1에 도착하는 데 추가로 8시간이 걸리고, 목적지인 별 2에 도착하는 데 다시 8시간이 더 걸린다.

참고: 이 문제의 배경인 우주에서는 빛의 속도가 시간당 1파섹보다 훨씬 빠르므로 특수 상대론적 효과를 걱정할 필요가 없다.