/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋くんは、頭パーツを 1 個と体パーツを 1 個組み合わせてロボットを 1 体作ることができます。 ロボットは頭パーツの重さが体パーツの重さより大きいと倒れてしまいます。
現在、高橋くんは頭パーツを N 個と体パーツを M 個持っています。 高橋くんが持っている i 番目 (1\le i\le N) の頭パーツの重さは H _ i グラム、i 番目 (1\le i\le M) の体パーツの重さは B _ i グラムです。
高橋くんは、持っているパーツを適切に組み合わせることで、倒れないロボットを合計 K 体作りたいです。 うまくパーツを組み合わせることで高橋くんが目標を達成することができるか判定してください。
ただし、1 個のパーツを複数のロボットを作るために利用したり、1 体のロボットを作るために頭パーツを 2 個以上（もしくは体パーツを 2 個以上）利用することはできません。
制約
- 1\le N\le2\times10 ^ 5
- 1\le M\le2\times10 ^ 5
- 1\le K\le\min\lbrace N,M\rbrace
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K H _ 1 H _ 2 \ldots H _ N B _ 1 B _ 2 \ldots B _ M
出力
高橋くんがパーツをうまく組み合わせて倒れないロボットを K 体作ることができるなら Yes を、そうでなければ No を出力せよ。
入力例 1
6 6 3 2 7 1 8 2 8 1 8 2 8 4 5
出力例 1
Yes
i 番目の頭パーツと j 番目の体パーツを組み合わせることを (i,j) と書くことにすると、高橋くんは例えば (1,2),(2,4),(3,6) のように組み合わせることで 3 体の倒れないロボットを作ることができます。
よって、Yes を出力してください。
入力例 2
1 1 1 43 1
出力例 2
No
高橋くんが持っている頭パーツが重すぎるため、高橋くんは倒れないロボットを作ることができません。
入力例 3
1 1 1 100 100
出力例 3
Yes
頭の重さと体の重さが等しい場合、ロボットは倒れないことに注意してください。
入力例 4
12 15 12 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772 155 506 832 854 353 465 387
出力例 4
Yes
Score : 300 points
Problem Statement
Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.
Currently, he has N head parts and M body parts. The weight of the i-th (1\le i\le N) head part is H _ i grams, and the weight of the i-th (1\le i\le M) body part is B _ i grams.
He wants to create a total of K robots that do not fall over by appropriately combining the parts he has. Determine whether he can achieve his goal by combining the parts well.
Here, a part cannot be used to create multiple robots, and two or more head parts (or two or more body parts) cannot be used to create one robot.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le M\le2\times10 ^ 5
- 1\le K\le\min\lbrace N,M\rbrace
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K H _ 1 H _ 2 \ldots H _ N B _ 1 B _ 2 \ldots B _ M
Output
Print Yes if Takahashi can combine the parts well to create K robots that do not fall over; otherwise, print No.
Sample Input 1
6 6 3 2 7 1 8 2 8 1 8 2 8 4 5
Sample Output 1
Yes
If we denote combining the i-th head part and the j-th body part as (i,j), then Takahashi can create three robots that do not fall over by combining them as (1,2),(2,4),(3,6), for example.
Thus, print Yes.
Sample Input 2
1 1 1 43 1
Sample Output 2
No
His head part is too heavy, so he cannot create any robot that does not fall over.
Sample Input 3
1 1 1 100 100
Sample Output 3
Yes
Note that a robot does not fall over if the head and body have equal weights.
Sample Input 4
12 15 12 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772 155 506 832 854 353 465 387
Sample Output 4
Yes