题目描述

Aninda 和 Boon-Nam 是一家小型艺术博物馆的保安。他们的工作包括 $N$ 个班次。在每个班次中，至少有一名保安必须工作。

两位保安对不同班次有不同的偏好。对于第 $i$ 个班次，如果 Aninda 工作，他将获得 $A_i$ 点幸福值；如果 Boon-Nam 工作，她将获得 $B_i$ 点幸福值。

如果两位保安都至少获得 $H$ 点幸福值，他们就会感到高兴。请问有多少种不同的班次分配方案能使保安们高兴？

如果存在某个班次，在一个方案中 Aninda 工作而在另一个方案中不工作，或者 Boon-Nam 工作而在另一个方案中不工作，则认为这两个方案不同。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $H$，分别表示班次数量和所需的最小幸福值。第二行包含 $N$ 个整数，其中第 $i$ 个整数是 $A_i$，表示如果 Aninda 在第 $i$ 个班次工作他能获得的幸福值。第三行包含 $N$ 个整数，其中第 $i$ 个整数是 $B_i$，表示如果 Boon-Nam 在第 $i$ 个班次工作她能获得的幸福值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是能使保安们高兴的不同班次分配方案数。

2
2 3
1 2
3 3
2 5
2 2
10 30

Case #1: 3
Case #2: 0

提示

在样例 #1 中，有 $N = 2$ 个班次，$H = 3$。有 $3$ 种方式使 Aninda 和 Boon-Nam 都高兴：

• 只有 Aninda 在第一个班次工作，而两人都在第二个班次工作。
• 两人都在第一个班次工作，而只有 Aninda 在第二个班次工作。
• 两名保安都在两个班次工作。

在样例 #2 中，有 $N = 2$ 个班次，$H = 5$。不可能使两人都高兴，因此答案为 $0$。

限制条件

$1 \le T \le 100$。

$0 \le H \le 10^9$。

$0 \le A_i \le 10^9$。

$0 \le B_i \le 10^9$。

测试集 1（可见）

$1 \le N \le 12$。

测试集 2（隐藏）

$1 \le N \le 20$。

翻译由 DeepSeek V4 Pro 完成