← 返回题目列表

AtCoder · joig2026final_j

J. 咖喱饭

中文机器翻译题面 查看原题

配点 : 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).
  • 所有输入值都是整数。

小課題

  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 满足约束。