B - Selection of Delivery Trucks Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は物流会社で働いています。会社の倉庫には N 台の配送トラックがあり、各トラックにはすでに荷物が積まれています。i 番目のトラック (1 \leq i \leq N) には W_i 個の荷物が積まれています。

今日は M 件の配送先があり、j 番目の配送先 (1 \leq j \leq M) には R_j 個以上の荷物を届けなければなりません。

今日出勤しているドライバーは K 人しかおらず、1台のトラックを出発させるには1人のドライバーが必要です。そのため、高橋君は N 台のトラックの中から K 台以下を選んで出発させることができます（1台も選ばなくてもよいですが、その場合届けられる荷物は0個です）。ただし、同じトラックを複数回選ぶことはできません。選ばれなかったトラックの荷物は使うことができません。

出発させたトラックに積まれている荷物は、すべてまとめて扱うことができます。すなわち、出発させたトラックの荷物の合計個数を S とするとき、高橋君は S 個の荷物を M 件の配送先に自由に振り分けることができます。各配送先に振り分ける個数は 0 個以上の整数であり、すべての配送先に振り分ける個数の合計は S 以下でなければなりません。荷物が余ることは問題ありません。

上司の青木君は「すべての配送先にそれぞれ必要な個数の荷物を届けられなければ、会社の信用に関わる」と厳しく言っています。

高橋君がトラックをうまく選ぶことで、すべての配送先 j (1 \leq j \leq M) にそれぞれ R_j 個以上の荷物を届けることが可能かどうかを判定してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M K
W_1 W_2 \ldots W_N
R_1 R_2 \ldots R_M
  • 1 行目には、トラックの台数を表す N 、配送先の件数を表す M 、ドライバーの人数を表す K が、スペース区切りで与えられる。
  • 2 行目には、各トラックに積まれている荷物の個数を表す W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
  • 3 行目には、各配送先が必要とする荷物の個数を表す R_1, R_2, \ldots, R_M が、スペース区切りで与えられる。

出力

すべての配送先に必要な荷物を届けることが可能な場合は Yes を、不可能な場合は No を出力してください。

入力例 1

4 3 2
10 25 15 30
12 18 20

出力例 1

Yes

入力例 2

3 2 1
10 20 15
15 10

出力例 2

No

入力例 3

8 6 4
50 20 80 10 40 70 30 60
45 55 30 70 25 35

出力例 3

Yes

入力例 4

15 10 6
350000000 820000000 190000000 950000000 410000000 630000000 280000000 770000000 500000000 120000000 890000000 640000000 310000000 480000000 730000000
580000000 910000000 340000000 720000000 660000000 450000000 830000000 290000000 510000000 170000000

出力例 4

No

入力例 5

1 1 1
1
1

出力例 5

Yes

Score : 300 pts

Problem Statement

Takahashi works at a logistics company. The company's warehouse has N delivery trucks, each already loaded with packages. The i-th truck (1 \leq i \leq N) is loaded with W_i packages.

Today there are M delivery destinations, and the j-th destination (1 \leq j \leq M) must receive at least R_j packages.

Only K drivers are on duty today, and one driver is needed to dispatch each truck. Therefore, Takahashi can select and dispatch at most K trucks from the N available trucks (he may also choose not to select any, but in that case the number of packages that can be delivered is 0). However, the same truck cannot be selected more than once. Packages on trucks that are not selected cannot be used.

The packages loaded on the dispatched trucks can all be handled together. That is, if the total number of packages on the dispatched trucks is S, Takahashi can freely distribute S packages among the M delivery destinations. The number of packages allocated to each destination must be a non-negative integer, and the total number of packages allocated across all destinations must be at most S. It is acceptable for packages to be left over.

Takahashi's boss, Aoki, has strictly stated: "If we cannot deliver the required number of packages to every delivery destination, the company's reputation will be at stake."

Determine whether it is possible for Takahashi to select trucks appropriately so that at least R_j packages are delivered to each delivery destination j (1 \leq j \leq M).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers

Input

N M K
W_1 W_2 \ldots W_N
R_1 R_2 \ldots R_M
  • The first line contains N (the number of trucks), M (the number of delivery destinations), and K (the number of drivers), separated by spaces.
  • The second line contains W_1, W_2, \ldots, W_N, the number of packages loaded on each truck, separated by spaces.
  • The third line contains R_1, R_2, \ldots, R_M, the number of packages required by each delivery destination, separated by spaces.

Output

If it is possible to deliver the required packages to all delivery destinations, print Yes; otherwise, print No.

Sample Input 1

4 3 2
10 25 15 30
12 18 20

Sample Output 1

Yes

Sample Input 2

3 2 1
10 20 15
15 10

Sample Output 2

No

Sample Input 3

8 6 4
50 20 80 10 40 70 30 60
45 55 30 70 25 35

Sample Output 3

Yes

Sample Input 4

15 10 6
350000000 820000000 190000000 950000000 410000000 630000000 280000000 770000000 500000000 120000000 890000000 640000000 310000000 480000000 730000000
580000000 910000000 340000000 720000000 660000000 450000000 830000000 290000000 510000000 170000000

Sample Output 4

No

Sample Input 5

1 1 1
1
1

Sample Output 5

Yes