Cutoff

题目描述

有一场按如下方式进行的考试。

考试由 $1$ 到 $N$ 共 $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$ 之间的整数。

输入格式

输入从标准输入给出，格式如下： $N$ $X$ $A_1$ $A_2$ $\dots$ $A_{N-1}$

输出格式

输出答案。

5 180
40 60 80 50

70

3 100
100 100

0

5 200
0 0 99 99

-1

10 480
59 98 88 54 70 24 8 94 46

45

提示

所有输入值均为整数。 $3 \le N \le 100$ $0 \le X \le 100 \times (N-2)$ $0 \le A_i \le 100$你在前四轮的得分是 $40$、$60$、$80$ 和 $50$.
如果你在第 $5$ 轮得到 $70$ 分，按非降序排列的得分序列为 $S=(40,50,60,70,80)$，最终成绩为 $50+60+70=180$.
可以证明 $70$ 是为了使最终成绩至少为 $180$ 所需的最小分数。
你在前两轮的得分是 $100$ 和 $100$.
如果你在第 $3$ 轮得到 $0$ 分，按非降序排列的得分序列为 $S=(0,100,100)$，最终成绩为 $100$.
注意最高分 $100$ 出现了多次，其中只有一个被排除。（最低分也是同理。）
可以证明 $0$ 是为了使最终成绩至少为 $100$ 所需的最小分数。
你在前四轮的得分是 $0$、$0$、$99$ 和 $99$.
可以证明无论你在第 $5$ 轮得到什么分数，最终成绩都不可能达到 $200$ 或更高。

标签: AtCoder|abc321B

来源

AtCoder|abc321B