← 返回题目列表

AtCoder · awc0095_b

B. 气球爆破游戏

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

分数: 333 分

问题陈述

高桥正在学校节日期间帮忙经营一个爆气球游戏摊位。有 N 气球在会场排成一排, i第气球的耐用性为 H_i.

高桥的团队有 M 飞镖,以及 j-th 飞镖的攻击力为 P_j.

高桥最多可以扔飞镖 总共 K 次。每次投掷时,他都会选择 1 飞镖从 M 飞镖和 1 气球来自 N 气球,然后将飞镖扔向那个气球。这会通过所选飞镖的攻击力来降低所选气球的耐用性。

每个飞镖可以使用任意次数。他还可以多次瞄准同一个气球,并且可以自由地向同一个气球投掷不同的飞镖。

当气球的耐久度变为 0 或更少,它会弹出。他也可以向已经爆破的气球投掷飞镖,但这样的投掷仍然算作他的投掷之一,并且不会增加爆破的气球的数量。

确定高桥以最佳方式投掷飞镖时可以弹出的最大气球数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq H_i \leq 10^{18} (1 \leq i \leq N)
  • 1 \leq P_j \leq 10^{18} (1 \leq j \leq M)
  • 所有输入值均为整数。

输入

N M K
H_1 H_2 \ldots H_N
P_1 P_2 \ldots P_M
  • 第一行包含气球数量 N, 飞镖数量 M,以及最大抛出次数 K,用空格分隔。
  • 第二行包含每个气球的耐久性 H_1, H_2, \ldots, H_N,用空格分隔。
  • 第三行包含每支飞镖的攻击力 P_1, P_2, \ldots, P_M,用空格分隔。

输出

在一行中打印以最佳方式投掷飞镖时可以弹出的最大气球数。


样本输入 1

5 2 5
3 1 4 1 5
2 3

示例输出 1

4

示例输入 2

3 1 2
10 20 30
5

示例输出 2

1

示例输入 3

7 3 15
10 5 8 12 3 7 20
4 6 2

示例输出 3

7

示例输入 4

10 5 50
100 200 300 400 500 600 700 800 900 1000
3 7 10 5 2

示例输出 4

2

示例输入 5

1 1 1
1
1

示例输出 5

1