C - ヘイホー君と最終試験

Contest Duration: 2015-11-15(Sun) 00:10 - 2015-11-15(Sun) 01:40 (local time) (90 minutes)

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$ を出力せよ。
どちらでもない場合、ヘイホー君が最終試験で取る必要のある最低点を出力せよ。

いずれの場合も、出力の末尾には改行をいれること。

入力例1Copy

Copy

出力例1Copy

Copy

ヘイホー君が最終試験で $45$ 点を取った場合、上位 $3$ 個の平均は $(86+49+45)/3=60$ となり、単位が認定されます。もちろん、 $46$ 点以上取っても単位は認定されます。一方、 $44$ 点以下の場合には単位が認定されません。

入力例2Copy

Copy

出力例2Copy

Copy

最終試験で $0$ 点でも単位が認定されます。

入力例3Copy

Copy

出力例3Copy

Copy

-1

残念ながら、最終試験が満点でも単位は認定されません。

入力例4Copy

Copy

13 10 1000000000 645245296
492014535
611893452
729291030
392019922
293849201
474839528
702912832
341845861
102495671
908590572
812912432
129855439

出力例4Copy

Copy

986132796

大きな数が入力されることもあります。オーバーフローに注意しましょう。