/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
以下の手順で行われる試験があります。
- 試験は 1 ラウンド目から N ラウンド目までの N ラウンドからなる。
- 各ラウンドに対し、 0 以上 100 以下の整数でスコアが与えられる。
- N ラウンドのスコアのうち、最高スコアと最低スコアを除いた N-2 ラウンドのスコアの合計が最終結果となる。
- 厳密には、各ラウンドのスコアを昇順に並べた列を S=(S_1,S_2,\dots,S_N) としたとき、最終結果は S_2+S_3+\dots+S_{N-1} となる。
現在、試験のうち N-1 ラウンドが終了し、 i ラウンド目のスコアは A_i でした。
最終結果を X 以上とするために N ラウンド目に取るべきスコアの最小値を出力してください。
但し、 N ラウンド目にどのようなスコアを取っても最終結果が X 以上にならない場合、代わりに -1 と出力してください。
なお、 N ラウンド目に取りうるスコアは 0 以上 100 以下の整数であることに注意してください。
制約
- 入力は全て整数
- 3 \le N \le 100
- 0 \le X \le 100 \times (N-2)
- 0 \le A_i \le 100
入力
入力は以下の形式で標準入力から与えられる。
N X
A_1 A_2 \dots A_{N-1}
出力
答えを出力せよ。
入力例 1
5 180 40 60 80 50
出力例 1
70
4 ラウンド目までのスコアは 40,60,80,50 でした。
5 ラウンド目にスコア 70 を取ると、スコアを昇順に並べた列は S=(40,50,60,70,80) となり、最終結果は 50+60+70=180 となります。
なお、最終結果を 180 以上にするために取るべきスコアの最小値が 70 であることが示せます。
入力例 2
3 100 100 100
出力例 2
0
2 ラウンド目までのスコアは 100,100 でした。
3 ラウンド目にスコア 0 を取ると、スコアを昇順に並べた列は S=(0,100,100) となり、最終結果は 100 となります。
最大スコアである 100 が複数ありますが、そのうち 1 つしか除かれないことに注意してください。(最小スコアについても同様です)
なお、最終結果を 100 以上にするために取るべきスコアの最小値が 0 であることが示せます。
入力例 3
5 200 0 0 99 99
出力例 3
-1
4 ラウンド目までのスコアは 0,0,99,99 でした。
5 ラウンド目にどのようなスコアを取っても、最終結果を 200 以上にすることができないことが示せます。
入力例 4
10 480 59 98 88 54 70 24 8 94 46
出力例 4
45
Score : 200 points
Problem Statement
There is an exam structured as follows.
- The exam consists of N rounds called round 1 to N.
- In each round, you are given an integer score between 0 and 100, inclusive.
- Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
- Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.
Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.
Constraints
- All input values are integers.
- 3 \le N \le 100
- 0 \le X \le 100 \times (N-2)
- 0 \le A_i \le 100
Input
The input is given from Standard Input in the following format:
N X
A_1 A_2 \dots A_{N-1}
Output
Print the answer.
Sample Input 1
5 180 40 60 80 50
Sample Output 1
70
Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.
Sample Input 2
3 100 100 100
Sample Output 2
0
Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.
Sample Input 3
5 200 0 0 99 99
Sample Output 3
-1
Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.
Sample Input 4
10 480 59 98 88 54 70 24 8 94 46
Sample Output 4
45