SP14883 GCJ121CC - Box Factory

你拥有一家工厂，有两条生产线。第一条生产线负责制造盒子，第二条生产线负责制造放入这些盒子的玩具。每种类型的盒子只能搭配对应类型的玩具。 在操作中，你首先从第一条生产线取一个盒子，同时从第二条生产线取一个玩具。接下来，你有以下几个选择： - 丢弃当前盒子并取下一个盒子； - 丢弃当前玩具并取下一个玩具； - 如果当前盒子和玩具属于同一类型，可以将玩具放入盒子并发送给客户。 需要注意的是，你总是按照生产顺序依次取盒子和玩具。已知两条生产线上的盒子和玩具的生产顺序。你的目标是设计一个策略，使得能够发送给客户的最大装有玩具的盒子数量最大化。 特别要注意：虽然两条生产线会制造大量的盒子和玩具，但通常会在相当长的时间内专注生产一种类型的物品，然后再切换到另一种类型。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$。接下来的两行分别描述了盒子和玩具的生产情况： - 第一行有 $2 \times N$ 个整数，依次为 $a_1, A_1, a_2, A_2, \ldots, a_N, A_N$，表示第一条生产线先生产 $a_1$ 个类型为 $A_1$ 的盒子，接着 $a_2$ 个类型为 $A_2$ 的盒子，依此类推，直到生产完 $a_N$ 个类型为 $A_N$ 的盒子。 - 第二行有 $2 \times M$ 个整数，依次为 $b_1, B_1, b_2, B_2, \ldots, b_M, B_M$，表示第二条生产线先生产 $b_1$ 个类型为 $B_1$ 的玩具，接着 $b_2$ 个类型为 $B_2$ 的玩具，依此类推，直到生产完 $b_M$ 个类型为 $B_M$ 的玩具。 玩具和盒子只有在类型号相同时才可以匹配。

对于每个测试用例，输出形式为 “Case #x: y”的字符串，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 是你可以发送给客户的最大装有玩具的盒子数量。

- 测试用例数量 $1 \le T \le 100$ - 每条生产线上，不同种类物品的段数 $1 \le N, M \le 10^5$ - 每种类型的盒子和玩具个数 $1 \le a_i, b_j \le 10^9$ - 物品类型号 $1 \le A_i, B_j \le 10^5$ **本翻译由 AI 自动生成**