P16743 [GKS 2019 #G] Shifts

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$ 是能使保安们高兴的不同班次分配方案数。

在样例 #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 完成