問題文

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

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

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

制約

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

小課題

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 点) 追加の制約はない．

入力例 1

3 4
2 2 2
4 1 1 1

出力例 1

6

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

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

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

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

入力例 2

3 4
4 2 4
1 4 3 1

出力例 2

8

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

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

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

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

入力例 3

2 2
1 1000000000
1000000000 1

出力例 3

3

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

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

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

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