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

葵は $ N $ 種類のカレーと， $ M $ 種類のライスを準備した． $ i $ 種類目 $ (1 \leqq i \leqq N) $ のカレーは $ A_i $ 皿分， $ j $ 種類目 $ (1 \leqq j \leqq M) $ のライスは $ B_j $ 皿分ある． $ 1 $ 皿分のカレーと $ 1 $ 皿分のライスを組み合わせることで， $ 1 $ 皿のカレーライスを作ることができる．

葵はビーバーたちにカレーライスを振る舞うことにした． $ 1 $ 匹のビーバーに対し $ 1 $ 皿のカレーライスを提供するが，ビーバーたちは大変個性的であるため，同じ種類のカレーライスを $ 2 $ 匹以上のビーバーが受け取ることはない．ただし，カレーとライスが両方とも同じ種類のとき，かつそのときに限り，同じ種類のカレーライスであるとみなす．

準備したカレーとライスでカレーライスを作るとき，最大で何匹のビーバーがカレーライスを受け取ることができるかを求めるプログラムを作成せよ．

---

入力は以下の形式で標準入力から与えられる．

$ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_M $

標準出力に，カレーライスを受け取ることのできるビーバーの最大数を $ 1 $ 行で出力せよ．

---

小課題

1. ( $ 6 $ 点) $ A_i = 1 $ ( $ 1 \leqq i \leqq N $ ), $ B_j = 1 $ ( $ 1 \leqq j \leqq 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 \leqq 2,000 $ ， $ B_1 + B_2 + \cdots + B_M \leqq 2,000 $ ．
6. ( $ 19 $ 点) $ A_1 + A_2 + \cdots + A_N \leqq 500,000 $ ， $ B_1 + B_2 + \cdots + B_M \leqq 500,000 $ ．
7. ( $ 22 $ 点) 追加の制約はない．

---

Sample Explanation 1

以下の組み合わせでカレーライスを用意する場合が考えられる．

• $ 1 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 1 $ 種類目のカレーと $ 2 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 3 $ 種類目のライス
• $ 3 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 3 $ 種類目のカレーと $ 4 $ 種類目のライス

このとき， $ 6 $ 匹のビーバーがカレーライスを受け取ることができる．また， $ 6 $ 匹より多いビーバーがカレーライスを受け取ることはできない．したがって， $ 6 $ を出力する．

この入力例は小課題 $ 4,5,6,7 $ の制約を満たす．

---

Sample Explanation 2

以下の組み合わせでカレーライスを用意する場合が考えられる．

• $ 1 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 1 $ 種類目のカレーと $ 2 $ 種類目のライス
• $ 1 $ 種類目のカレーと $ 3 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 2 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 3 $ 種類目のライス
• $ 3 $ 種類目のカレーと $ 2 $ 種類目のライス
• $ 3 $ 種類目のカレーと $ 3 $ 種類目のライス
• $ 3 $ 種類目のカレーと $ 4 $ 種類目のライス

このとき， $ 8 $ 匹のビーバーがカレーライスを受け取ることができる．また， $ 8 $ 匹より多いビーバーがカレーライスを受け取ることはできない．したがって， $ 8 $ を出力する．

この入力例は小課題 $ 5,6,7 $ の制約を満たす．

---

Sample Explanation 3

以下の組み合わせでカレーライスを用意する場合が考えられる．

• $ 1 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 1 $ 種類目のライス
• $ 2 $ 種類目のカレーと $ 2 $ 種類目のライス

このとき， $ 3 $ 匹のビーバーがカレーライスを受け取ることができる．また， $ 3 $ 匹より多いビーバーがカレーライスを受け取ることはできない．したがって， $ 3 $ を出力する．

この入力例は小課題 $ 2,3,5,6,7 $ の制約を満たす．

Constraints

• $ 1 \leqq N \leqq 500,000 $ ．
• $ 1 \leqq M \leqq 500,000 $ ．
• $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )．
• $ 1 \leqq B_j \leqq 10^9 $ ( $ 1 \leqq j \leqq M $ )．
• 入力される値はすべて整数である．