AT_joig2026final_j カレーライス (Curry and Rice)

葵准备了 $N$ 种咖喱和 $M$ 种米饭。第 $i$ 种咖喱有 $A_i$ 份，第 $j$ 种米饭有 $B_j$ 份。可以将 $1$ 份咖喱和 $1$ 份米饭组合成一份咖喱饭。 葵想要请海狸们吃咖喱饭。每只海狸可以获得一份咖喱饭，但由于海狸们各具特色，不能有 $2$ 只或以上的海狸获得完全相同种类的咖喱饭。这里，“同种类的咖喱饭”指的是同时由同一种咖喱和同一种米饭组成的咖喱饭，仅当咖喱和米饭种类都相同时才算相同。 请编写程序，计算最多能让多少只海狸获得咖喱饭。 ---

输入以如下格式从标准输入读取： > $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$

输出能够获得咖喱饭的海狸的最大数量，输出一行。 ---

### 子任务 1. ($6$ 分) $A_i = 1$ ($1 \leq i \leq N$)，$B_j = 1$ ($1 \leq j \leq M$)。 2. ($7$ 分) $N = M = 2$。 3. ($12$ 分) $N = 2$。 4. ($14$ 分) $A_1 = A_2 = \dots = A_N$。 5. ($20$ 分) $A_1 + A_2 + \cdots + A_N \leq 2\,000$，$B_1 + B_2 + \cdots + B_M \leq 2\,000$。 6. ($19$ 分) $A_1 + A_2 + \cdots + A_N \leq 500\,000$，$B_1 + B_2 + \cdots + B_M \leq 500\,000$。 7. ($22$ 分) 无其它附加限制。 --- ### 样例解释 1 以下为一种可行的咖喱饭组合方式： - 第 $1$ 种咖喱 + 第 $1$ 种米饭 - 第 $1$ 种咖喱 + 第 $2$ 种米饭 - 第 $2$ 种咖喱 + 第 $1$ 种米饭 - 第 $2$ 种咖喱 + 第 $3$ 种米饭 - 第 $3$ 种咖喱 + 第 $1$ 种米饭 - 第 $3$ 种咖喱 + 第 $4$ 种米饭 此时有 $6$ 只海狸能获得咖喱饭，而且无法让超过 $6$ 只海狸吃到咖喱饭。因此，输出 $6$。 此输入同时满足子任务 $4,5,6,7$ 的限制。 --- ### 样例解释 2 以下为一种可行的咖喱饭组合方式： - 第 $1$ 种咖喱 + 第 $1$ 种米饭 - 第 $1$ 种咖喱 + 第 $2$ 种米饭 - 第 $1$ 种咖喱 + 第 $3$ 种米饭 - 第 $2$ 种咖喱 + 第 $2$ 种米饭 - 第 $2$ 种咖喱 + 第 $3$ 种米饭 - 第 $3$ 种咖喱 + 第 $2$ 种米饭 - 第 $3$ 种咖喱 + 第 $3$ 种米饭 - 第 $3$ 种咖喱 + 第 $4$ 种米饭 此时有 $8$ 只海狸能获得咖喱饭，而且无法让超过 $8$ 只海狸吃到咖喱饭。因此，输出 $8$。 此输入同时满足子任务 $5,6,7$ 的限制。 --- ### 样例解释 3 以下为一种可行的咖喱饭组合方式： - 第 $1$ 种咖喱 + 第 $1$ 种米饭 - 第 $2$ 种咖喱 + 第 $1$ 种米饭 - 第 $2$ 种咖喱 + 第 $2$ 种米饭 此时有 $3$ 只海狸能获得咖喱饭，而且无法让超过 $3$ 只海狸吃到咖喱饭。因此，输出 $3$。 此输入同时满足子任务 $2,3,5,6,7$ 的限制。 # 数据范围与限制 - $1 \leq N \leq 500\,000$。 - $1 \leq M \leq 500\,000$。 - $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$)。 - $1 \leq B_j \leq 10^9$ ($1 \leq j \leq M$)。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译