바나나 송이

Barbara는 Alan의 바나나 농장에 간다. 그곳에는 $\mathbf{N}$그루의 바나나 나무가 배열 $\mathbf{B}$로 표현되는 하나의 긴 줄에 배치되어 있다. 위치 $i$의 나무에는 바나나 송이가 $\mathbf{B_i}$개 있다. 각 나무의 가격은 같다. Barbara가 나무 한 그루를 사면 그 나무에 있는 바나나 송이를 모두 얻는다. Alan에게는 특별한 규칙이 있다. 나무가 늘어선 줄에 빈틈이 너무 많이 생기는 것을 원하지 않기 때문에, Alan은 Barbara가 바나나 나무가 늘어선 줄에서 최대 $2$개의 연속 구간만 살 수 있도록 허용한다.

Barbara는 구매한 나무에 있는 바나나 송이의 총수가 자신의 바구니 용량인 $\mathbf{K}$와 같도록 나무 몇 그루를 사고자 한다. 이때 가능한 한 적은 돈을 쓰고자 한다. 나무를 몇 그루 사야 하는가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1$부터 $\mathbf{N}$까지의 각 $i$에 대해 $0 \le \mathbf{B_{i}} \le \mathbf{K}$.

테스트 세트 1

$1 \le \mathbf{K} \le 10^4$. $1 \le \mathbf{N} \le 50$.

테스트 세트 2

$1 \le \mathbf{K} \le 10^4$. $1 \le \mathbf{N} \le 500$.

테스트 세트 3

$1 \le \mathbf{K} \le 10^6$.

최대 25개의 케이스에 대해: $1 \le \mathbf{N} \le 5000$.

나머지 케이스에 대해: $1 \le \mathbf{N} \le 500$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Alan의 농장에 있는 나무의 수 $\mathbf{N}$와 Barbara의 바구니 용량 $\mathbf{K}$라는 두 정수를 포함하는 한 줄로 시작한다. 다음 줄에는 배열 $\mathbf{B}$을 나타내는 $\mathbf{N}$개의 음이 아닌 정수 $\mathbf{B_1}, \mathbf{B_2},\dots, \mathbf{B_N}$가 주어지며, $i$번째 정수는 Alan의 농장에 있는 $i$번째 나무의 바나나 송이 수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$은 농장의 최대 $2$개 연속 구간을 사용하여 바나나 송이 $\mathbf{K}$개를 얻기 위해 Barbara가 구매해야 하는 나무의 최소 수이며, 그렇게 하는 것이 불가능하면 -1이다.

예제 케이스 #1에서 첫 번째 구간은 인덱스 $2$와 $3$의 나무를 포함할 수 있고, 두 번째 구간은 인덱스 $6$의 나무를 포함할 수 있다.

예제 케이스 #2에서는 $2$개의 연속 구간으로 합 $10$을 만드는 것이 불가능하다.

예제 케이스 #3에서 첫 번째 구간은 인덱스 $\{1, 2\}$의 나무를 포함할 수 있고, 두 번째 구간은 인덱스 $\{5, 6\}$의 나무를 포함할 수 있다. $2 + 3 + 3$ 조합(인덱스 $\{1, 3, 5\}$의 나무)은 $3$개의 연속 구간이 되므로 선택할 수 없다.

예제 케이스 #4에서 유일한 구간은 인덱스 $\{1, 2, 3\}$의 나무를 포함한다.