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 $ )． - 入力される値はすべて整数である．