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

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

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