Problem Description

In the competitive programming class at Codefes University, they conduct $ N $ exams for grading purposes. Each exam score is an integer between $ 0 $ and $ M $ inclusive. If the average of the top $ K $ scores among the $ N $ exam scores is at least $ R $ points, the student will be awarded a passing grade. If the average of the top $ K $ scores is less than $ R $ points, the student will fail and not be awarded a passing grade.

Heyho-kun is about to take the final exam after completing $ N-1 $ exams. His scores in the $ N-1 $ exams are $ S_1 $, $ S_2 $, ..., $ S_{N-1} $ points respectively. What is the minimum score Heyho-kun needs to achieve in the final exam to be awarded a passing grade?

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ M $ $ R $ $ S_1 $ $ S_2 $ : $ S_{N-1} $

• The first line contains integers $N\ (1\ ≦\ N\ ≦\ 100)$, $K\ (1\ ≦\ K\ ≦\ N)$, $M\ (1\ ≦\ M\ ≦\ 10^9)$, $R\ (0\ ≦\ R\ ≦\ M)$, separated by spaces. Here, $ N $ is the number of exams, $ K $ is the number of exams used for grading, $ M $ is the maximum score for each exam, and $ R $ is the required average score for passing.
• The next $ N-1 $ lines contain integers $S_i\ (0\ ≦\ S_i\ ≦\ M)$, representing Heyho-kun's scores in the $ i $th exam.
• Note that $ S_N $ is not given.

Output Format

The output consists of one line:

• If Heyho-kun is guaranteed to pass regardless of his final exam score, output $ 0 $.
• If Heyho-kun is guaranteed to fail regardless of his final exam score, output $ -1 $.
• Otherwise, output the minimum score Heyho-kun needs to achieve in the final exam.

In all cases, end the output with a newline.

Sample Input and Output

Sample Input #1

5 3 100 60
86
23
49
39

Sample Output #1

45

Sample Input #2

5 3 100 60
92
100
95
99

Sample Output #2

0

Sample Input #3

5 3 100 60
18
42
29
31

Sample Output #3

-1

Sample Input #4

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

Sample Output #4

986132796

Notes/Hints

Sample Explanation 1

If Heyho-kun scores $ 45 $ points in the final exam, the average of the top $ 3 $ scores is $ (86+49+45)/3=60 $, which is enough to pass. Of course, scoring $ 46 $ points or more will also result in passing. However, scoring $ 44 $ points or less will result in failure.

Sample Explanation 2

Even if Heyho-kun scores $ 0 $ points in the final exam, he will still pass.

Sample Explanation 3

Unfortunately, even if Heyho-kun scores the maximum points in the final exam, he will still fail.

Sample Explanation 4

Large numbers may be given as input. Be cautious of overflow.

见题面 Input 部分

见题面 Output 部分