B - 風船割りゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は文化祭で風船割りゲームの出店を手伝っています。会場には N 個の風船が一列に並んでおり、i 番目の風船の耐久値は H_i です。

高橋君のチームには M 本のダーツがあり、j 番目のダーツの攻撃力は P_j です。

高橋君は合計で K 回以下、ダーツを投げることができます。1 回の投擲（とうてき）では、M 本のダーツの中から 1 本を選び、N 個の風船の中から 1 個を選んで、その風船にダーツを投げます。これにより、選んだ風船の耐久値が選んだダーツの攻撃力の分だけ減少します。

各ダーツは何度でも繰り返し使うことができます。また、同じ風船を何度狙ってもよく、1 つの風船に対して異なるダーツを投げることも自由にできます。

風船の耐久値が 0 以下になると、その風船は割れます。すでに割れた風船にダーツを投げることもできますが、その投擲は 1 回分として数えられ、割れた風船の数が増えることはありません。

高橋君が最適にダーツを投げたとき、割れる風船の数の最大値を求めてください。

制約

  • 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
  • 1 行目には、風船の数 N、ダーツの本数 M、投擲回数の上限 K が、スペース区切りで与えられる。
  • 2 行目には、各風船の耐久値 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 3 行目には、各ダーツの攻撃力 P_1, P_2, \ldots, P_M が、スペース区切りで与えられる。

出力

最適にダーツを投げたときに割れる風船の最大数を 1 行で出力せよ。

入力例 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

Score : 333 pts

Problem Statement

Takahashi is helping run a balloon popping game booth at a school festival. There are N balloons lined up in a row at the venue, and the i-th balloon has a durability of H_i.

Takahashi's team has M darts, and the j-th dart has an attack power of P_j.

Takahashi can throw darts at most K times in total. In each throw, he chooses 1 dart from the M darts and 1 balloon from the N balloons, and throws that dart at that balloon. This reduces the chosen balloon's durability by the chosen dart's attack power.

Each dart can be used any number of times. He may also target the same balloon multiple times, and is free to throw different darts at the same balloon.

When a balloon's durability becomes 0 or less, it pops. He may also throw darts at already popped balloons, but such a throw still counts as one of his throws, and it does not increase the number of popped balloons.

Determine the maximum number of balloons that can be popped when Takahashi throws darts optimally.

Constraints

  • 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)
  • All input values are integers.

Input

N M K
H_1 H_2 \ldots H_N
P_1 P_2 \ldots P_M
  • The first line contains the number of balloons N, the number of darts M, and the maximum number of throws K, separated by spaces.
  • The second line contains the durability of each balloon H_1, H_2, \ldots, H_N, separated by spaces.
  • The third line contains the attack power of each dart P_1, P_2, \ldots, P_M, separated by spaces.

Output

Print in one line the maximum number of balloons that can be popped when darts are thrown optimally.

Sample Input 1

5 2 5
3 1 4 1 5
2 3

Sample Output 1

4

Sample Input 2

3 1 2
10 20 30
5

Sample Output 2

1

Sample Input 3

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

Sample Output 3

7

Sample Input 4

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

Sample Output 4

2

Sample Input 5

1 1 1
1
1

Sample Output 5

1