C - ヘイホー君と最終試験
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
Codefes大学の競技プログラミングの授業では、成績評価のために、N 回の試験を行うことにしています。 各試験での成績は、0 以上 M 以下の整数値です。 N 個の試験成績のうち、上位 K 個の平均が R 点以上であれば、めでたく単位が認定されます。 上位 K 個の平均が R 点未満の場合には不合格となり、単位は認定されません。
N-1 回の試験を終えたヘイホー君は、最終試験に臨もうとしています。 最終試験を除く N-1 回の試験におけるヘイホー君の成績は、それぞれ S_1, S_2, …, S_{N-1} 点でした。 ヘイホー君は、最終試験で何点以上取れば単位が認定されるでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N K M R
S_1
S_2
:
S_{N-1}
- 1 行目には、整数 N (1 ≦ N ≦ 100), K (1 ≦ K ≦ N), M (1 ≦ M ≦ 10^9), R (0 ≦ R ≦ M) が、空白区切りで与えられる。 ここで、N は試験の回数、K は成績評価に用いる試験の個数、M は各試験の満点、R は単位認定に必要な平均点を表す。
- 2 行目以降の N-1 行には、整数 S_i (0 ≦ S_i ≦ M) が与えられる。これは i 回目の試験におけるヘイホー君の成績を表す。
- S_N が与えられないことに注意せよ。
出力
出力は 1 行からなる。
- 最終試験の結果が何点であってもヘイホー君に単位が認定されるならば、0 を出力せよ。
- 最終試験の結果が何点であってもヘイホー君に単位が認定されないならば、-1 を出力せよ。
- どちらでもない場合、ヘイホー君が最終試験で取る必要のある最低点を出力せよ。
いずれの場合も、出力の末尾には改行をいれること。
入力例1
5 3 100 60 86 23 49 39
出力例1
45
ヘイホー君が最終試験で 45 点を取った場合、上位 3 個の平均は (86+49+45)/3=60 となり、単位が認定されます。 もちろん、46 点以上取っても単位は認定されます。 一方、44 点以下の場合には単位が認定されません。
入力例2
5 3 100 60 92 100 95 99
出力例2
0
最終試験で 0 点でも単位が認定されます。
入力例3
5 3 100 60 18 42 29 31
出力例3
-1
残念ながら、最終試験が満点でも単位は認定されません。
入力例4
13 10 1000000000 645245296 492014535 611893452 729291030 392019922 293849201 474839528 702912832 341845861 102495671 908590572 812912432 129855439
出力例4
986132796
大きな数が入力されることもあります。オーバーフローに注意しましょう。