103211: [Atcoder]ABC321 B - Cutoff

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

问题描述

本次考试结构如下：

• 考试由$N$轮组成，分别称为第$1$轮到第$N$轮。
• 在每轮中，你会得到一个介于$0$和$100$之间的整数分数。
• 你的最终成绩是除最高分和最低分外的$N-2$轮的分数之和。
  • 形式上，假设$S=(S_1,S_2,\dots,S_N)$是你在每轮中获得的分数序列，按升序排列，那么最终成绩是$S_2+S_3+\dots+S_{N-1}$。

现在，已经进行了$N-1$轮考试，你在第$i$轮的成绩是$A_i$。
输出你在第$N$轮至少要获得多少分才能使最终成绩达到$X$或更高。
如果你在第$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

你在前四轮的分数分别是$40$、$60$、$80$和$50$。
如果你在第五轮获得$70$分，分数按升序排列的序列将为$S=(40,50,60,70,80)$，最终成绩为$50+60+70=180$。
可以证明，要使最终成绩达到$180$或更高，$70$是最小必须获得的分数。

样例输入2

3 100
100 100

样例输出2

0

你在前两轮的分数分别是$100$和$100$。
如果你在第三轮获得$0$分，分数按升序排列的序列将为$S=(0,100,100)$，最终成绩为$100$。
注意，最高分$100$出现了多次，只排除其中一次（最低分也一样）。
可以证明，要使最终成绩达到$100$或更高，$0$是最小必须获得的分数。

样例输入3

5 200
0 0 99 99

样例输出3

-1

你在前四轮的分数分别是$0$、$0$、$99$和$99$。
可以证明，无论你在第五轮获得多少分，你的最终成绩永远不会达到$200$或更高。

样例输入4

10 480
59 98 88 54 70 24 8 94 46

样例输出4

45