Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
PAKEN学園に通うOsmium_1008君は、課題を N 個こなさないといけません。
初め、Osmium_1008君のエネルギーは E あり、 i 個目の課題を終わらせるためには A_i のエネルギーを消費する必要があります。エネルギーが 0 より小さくなるようには行動できません。
どうしても課題が終わりそうにないOsmium_1008君は、エナジードリンクを飲むことにしました。エナジードリンクは M 本あり、j 本目のエナジードリンクを飲むとエネルギーが B_j 増えます。
しかし、Osmium_1008君は健康を気にしているため、できる限りエナジードリンクを飲みたくなく、多くても K 本までしか飲みません。
さて、Osmium_1008君が全ての課題を終えることができるかを判定し、終えることができるなら飲まなければいけないエナジードリンクの本数の最小値、終えることができないなら終わらせられる課題の数の最大値を出力してください。
制約
- 入力は全て整数である。
- 1\leq N,M\leq 2\times 10^5
- 1\leq K\leq M
- 0\leq E\leq 10^8
- 1\leq A_i,B_j\leq 10^8
- A_1+A_2+\ldots +A_{N-1}+A_N>E
入力
入力は以下の形式で標準入力から与えられます。
N M K E
A_1 A_2 \ldots A_{N-1} A_N
B_1 B_2 \ldots B_{M-1} B_M
出力
課題を終えることができるなら Yes
と出力し、次の行にエナジードリンクを飲む最低の本数を出力してください。
できないなら No
と出力し、次の行に終わらせられる最大の課題の数を出力してください。
入力例1
4 5 3 1
5 2 6 5
6 3 4 8 2
出力例1
Yes
3
エナジードリンク {1, 2, 4} を飲めばエネルギーが 18 となり、全ての課題を終えるのに必要なエネルギーに達するため課題を終えることができます。
3 本より少ない本数のエナジードリンクを飲むことによって課題を終えることはできません。
入力例2
4 5 2 1
5 2 6 5
6 3 4 8 2
出力例2
No
3
エナジードリンクをどのような組み合わせで飲んでもエネルギー量はすべての課題を終えるのに必要なエネルギーに達しないため、全ての課題を終わらせることはできません。エナジードリンク {3, 4} を飲めば課題 {1, 2, 4} を終わらせることができるので、終わらせられる最大の課題の数は 3 つです。
入力例3
1 15 14 86
92
47 98 3 71 37 46 87 39 75 65 100 44 91 85 52
出力例3
Yes
1
入力例4
20 1 1 91
40 66 82 48 3 46 25 51 65 12 96 66 40 97 100 13 62 98 6 1
68
出力例4
No
8
writer: Osmium_1008