Description

你拥有一家拥有两条装配线的工厂。第一条装配线生产盒子，第二条装配线生产可以放入这些盒子的玩具。每种类型的盒子只对应一种类型的玩具，反之亦然。

一开始，你会从第一条装配线上取一个盒子，从第二条装配线上取一个玩具。此时你有如下几种选择：

• 你可以随时丢弃盒子，取下一个盒子。
• 你可以随时丢弃玩具，取下一个玩具。
• 如果盒子和玩具是同一种类型，你可以将玩具放入盒子，并将其发给客户。

你总是按照生产顺序依次取盒子和玩具。你已知盒子和玩具的生产顺序，并希望制定一种策略，使得你发出的装盒玩具数量尽可能多。

注意：两条装配线会生产大量盒子和玩具，但它们通常会长时间连续生产同一种类型后才切换。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。

每组测试数据第一行为两个整数 $N$ 和 $M$。接下来一行为 $2 \times N$ 个整数 $a_1, A_1, a_2, A_2, \dots, a_N, A_N$，再接下来一行为 $2 \times M$ 个整数 $b_1, B_1, b_2, B_2, \dots, b_M, B_M$。

这表示第一条装配线会先生产 $a_1$ 个类型为 $A_1$ 的盒子，然后生产 $a_2$ 个类型为 $A_2$ 的盒子，依此类推，直到最后生产 $a_N$ 个类型为 $A_N$ 的盒子。第二条装配线同理，先生产 $b_1$ 个类型为 $B_1$ 的玩具，接着 $b_2$ 个类型为 $B_2$ 的玩具，依此类推，直到最后生产 $b_M$ 个类型为 $B_M$ 的玩具。

只有当盒子和玩具类型编号相同时，二者才能配对。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为你最多能发出的装盒玩具数量。

4
3 3
10 1 20 2 25 3
10 2 30 3 20 1
3 5
10 1 6 2 10 1
5 1 3 2 10 1 3 2 5 1
3 5
10 1 6 2 10 1
5 1 6 2 10 1 6 2 5 1
1 1
5000000 10
5000000 100

Case #1: 35
Case #2: 20
Case #3: 21
Case #4: 0

Hint

限制条件

• $1 \leq T \leq 100$
• $1 \leq a_i, b_i \leq 10^{16}$
• $1 \leq A_i, B_i \leq 100$

测试集 1（12 分，结果可见）

• $1 \leq N \leq 3$
• $1 \leq M \leq 100$

测试集 2（23 分，结果隐藏）

• $1 \leq N, M \leq 100$

翻译由 ChatGPT-4.1 完成。