题目描述

Barbara 前往 Alan 的香蕉农场，农场中有 $N$ 棵香蕉树排成一行，用一个数组 $B$ 表示。位置 $i$ 上的树有 $B_i$ 串香蕉。每棵树的成本相同。一旦 Barbara 购买了一棵树，她就获得该树上所有的香蕉串。

Alan 有一个特殊规则：因为他不想在行中留下太多空隙，所以他允许 Barbara 最多购买香蕉树行中的 $2$ 个连续段。

Barbara 希望购买一些树，使得这些树上的香蕉串总数恰好等于她篮子的容量 $K$。她希望在花费尽可能少的钱的前提下实现这一点。她应该购买多少棵树？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数：$N$（Alan 农场中香蕉树的数量）和 $K$（Barbara 篮子的容量）。

下一行包含 $N$ 个非负整数 $B_1, B_2, \dots, B_N$，表示数组 $B$，其中第 $i$ 个整数表示 Alan 农场中第 $i$ 棵树的香蕉串数量。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Barbara 使用最多 $2$ 个连续段获得恰好 $K$ 串香蕉所需购买的最少树的数量，如果不可能则输出 -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

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

提示

在样例 #1 中，第一个连续段可以包含索引 $2$ 和 $3$ 的树，第二个连续段可以包含索引 $6$ 的树。

在样例 #2 中，无法用 $2$ 个连续段得到总和 $10$。

在样例 #3 中，第一个连续段可以包含索引 $\{1, 2\}$ 的树，第二个连续段可以包含索引 $\{5, 6\}$ 的树。我们不能取 $2 + 3 + 3$ 的组合（索引 $\{1, 3, 5\}$ 的树），因为那将是 $3$ 个连续段。

在样例 #4 中，唯一的连续段包含索引 $\{1, 2, 3\}$ 的树。

限制条件

$1 \le T \le 100$。

对于每个 $i$ 从 $1$ 到 $N$，$0 \le B_i \le K$。

测试集 1

$1 \le K \le 10^4$。

$1 \le N \le 50$。

测试集 2

$1 \le K \le 10^4$。

$1 \le N \le 500$。

测试集 3

$1 \le K \le 10^6$。

最多 $25$ 个测试用例满足：

$1 \le N \le 5000$。

其余测试用例满足：

$1 \le N \le 500$。

翻译由 DeepSeek V4 Pro 完成