Description

准备好！Charles 和 Delila 即将在剑术大师击剑锦标赛的决赛中一决高下。

在击剑场的一面墙上，有一个剑架，上面放着 $N$ 种不同类型的剑；这些剑按照类型编号，从 $1$ 到 $N$。作为主裁判，你将选择一对整数 $(L, R)$（满足 $1 \leqslant L \leqslant R \leqslant N$），只有第 $L$ 种到第 $R$ 种（包含两端）的剑可以用于本场比赛。

不同类型的剑使用方式各异，擅长一种剑并不意味着擅长另一种！Charles 和 Delila 分别对第 $i$ 种剑的熟练度为 $C_i$ 和 $D_i$。他们会查看你为本场比赛指定的可用剑的类型，然后各自选择自己最擅长的一种剑。如果有多种可用类型的剑熟练度相同，且该熟练度高于其他所有可用类型，则选手会在这些同样擅长的类型中随机选择一种。注意，Charles 和 Delila 可能会选择同一种剑，这没有问题——每种剑有多把可用。

如果 Charles 选择的剑类型的熟练度与 Delila 选择的剑类型的熟练度之差的绝对值不超过 $K$，则这场比赛是“公平”的。为了让比赛更精彩，你想知道有多少种不同的 $(L, R)$ 选择会导致一场公平的比赛。

Input Format

第一行输入测试用例的数量 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行包含两个整数 $N$ 和 $K$，含义如上所述。接下来两行，每行包含 $N$ 个整数。第一行为 $C_i$，表示 Charles 对每种剑的熟练度。第二行为 $D_i$，表示 Delila 对每种剑的熟练度。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是能导致公平比赛的 $(L, R)$ 选择的数量。

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

Case #1: 4
Case #2: 4
Case #3: 1
Case #4: 0
Case #5: 1
Case #6: 7

Hint

样例解释

• 样例 1 中，只有当 Charles 能使用最后一种剑时，比赛才是公平的，所以答案是 $4$。
• 样例 2 中，有 $4$ 种公平的比赛区间：$(1, 2)$、$(1, 3)$、$(2, 2)$ 和 $(2, 3)$。注意，对于像 $(1, 3)$ 这样的区间，Charles 和 Delila 都有多种最擅长的剑可以选择；但每个区间只计为一次公平比赛。
• 样例 3 中，只有 $1$ 种公平比赛：$(1, 1)$。
• 样例 4 中，没有公平比赛，所以答案是 $0$。
• 样例 5 中，要注意选手不会为了让比赛公平而选择较弱的剑。例如 $(1, 3)$ 不是公平比赛，因为 Charles 会选择第一种剑，Delila 会选择第三种剑。Delila 不会为了照顾 Charles 而选择较弱的剑！
• 样例 6 中，有 $7$ 种公平比赛区间：$(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$、$(3, 3)$、$(3, 4)$ 和 $(4, 4)$。

数据范围

• $1 \leqslant T \leqslant 100$。
• $0 \leqslant K \leqslant 10^5$。
• $0 \leqslant C_i \leqslant 10^5$，对于所有 $i$。
• $0 \leqslant D_i \leqslant 10^5$，对于所有 $i$。

测试点 1（14 分，公开）

• $1 \leqslant N \leqslant 100$。

测试点 2（28 分，隐藏）

• 有 8 个测试用例满足 $N = 10^5$。
• 除这 8 个测试用例外，其余均满足 $1 \leqslant N \leqslant 1000$。

由 ChatGPT 4.1 翻译