配点 : 100 点
問題文
葵是 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 \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).
- 所有输入值都是整数。
小課題
- (6 点) A_i = 1 (1 \leqq i \leqq N), B_j = 1 (1 \leqq j \leqq M).
- (7 点) N = M = 2.
- (12 点) N = 2.
- (14 点) A_1 = A_2 = \dots = A_N.
- (20 点) A_1 + A_2 + \cdots + A_N \leqq 2\,000,B_1 + B_2 + \cdots + B_M \leqq 2\,000.
- (19 点) A_1 + A_2 + \cdots + A_N \leqq 500\,000,B_1 + B_2 + \cdots + B_M \leqq 500\,000.
- (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 满足约束。