시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB411100.000%

문제

Barbara goes to Alan's banana farm, where the $N$ banana trees are organized in one long line represented by an array $B$. The tree at position $i$ has $B_i$ banana bunches. Each tree has the same cost. Once Barbara buys a tree, she gets all the banana bunches on that tree. Alan has a special rule: because he does not want too many gaps in his line, he allows Barbara to buy at most $2$ contiguous sections of his banana tree line.

Barbara wants to buy some number of trees such that the total number of banana bunches on these purchased trees equals the capacity $K$ of her basket. She wants to do this while spending as little money as possible. How many trees should she buy?

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case begins with a line containing two integers integer $N$, the number of trees on Alan's farm, and $K$, the capacity of Barbara's basket.

The next line contains $N$ non-negative integers $B_1,B_2,\cdots,B_N$ representing array $B$, where the $i$-th integer represents the number of banana bunches on the $i$-th tree on Alan's farm.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the minimum number of trees Barbara must purchase to obtain $K$ banana bunches using at most $2$ contiguous sections of the farm, or -1 if it is impossible to do so.

제한

  • $1 \le T \le 100$.
  • $0 \le B_i \le K$, for each $i$ from $1$ to $N$.

Test Set 1 (8점)

  • $1 \le K\le 10^4$.
  • $1 \le N \le 50$.

Test Set 2 (11점)

  • $1 \le K\le 10^4$.
  • $1 \le N \le 500$.

Test Set 3 (14점)

  • $1 \le K\le 10^6$.

For at most 25 cases:

  • $1 \le N \le 5000$.

For the remaining cases:

  • $1 \le N \le 500$.

예제 입력 1

4
6 8
1 2 3 1 2 3
4 10
6 7 5 2
6 8
3 1 2 1 3 1
4 6
3 1 2 0

예제 출력 1

Case #1: 3
Case #2: -1
Case #3: 4
Case #4: 3

In Sample Case #1, the first section can contain the trees at indices $2$ and $3$, and the second section can contain the tree at index $6$.

In Sample Case #2, it is impossible to achieve a sum of $10$ with $2$ contiguous sections.

In Sample Case #3, the first section can contain the trees at indices $\{1,2\}$, and the second section can contain the trees at indices $\{5,6\}$. We cannot take the $2+3+3$ combo (trees at indices $\{1,3,5\}$) since that would be $3$ contiguous sections.

In Sample Case #4, the only section contains the trees at indices $\{1,2,3\}$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.