AT_abc321_b [ABC321B] Cutoff

题目描述

有一个按照以下步骤进行的考试。

• 考试共分为 $N$ 轮，从第 $1$ 轮到第 $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$ 之间的整数。

输入格式

输入以如下格式从标准输入读入。

$N$ $X$ $A_1$ $A_2$ $\dots$ $A_{N-1}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 180
40 60 80 50

输出 #1

70

输入输出样例 #2

输入 #2

3 100
100 100

输出 #2

0

输入输出样例 #3

输入 #3

5 200
0 0 99 99

输出 #3

-1

输入输出样例 #4

输入 #4

10 480
59 98 88 54 70 24 8 94 46

输出 #4

45

说明/提示

限制条件

• 输入均为整数。
• $3 \leq N \leq 100$
• $0 \leq X \leq 100 \times (N-2)$
• $0 \leq A_i \leq 100$

样例解释 1

前 $4$ 轮的分数为 $40,60,80,50$。如果第 $5$ 轮取得 $70$ 分，则分数升序排列为 $S=(40,50,60,70,80)$，最终结果为 $50+60+70=180$。可以证明，为了使最终结果不少于 $180$，第 $5$ 轮至少需要取得 $70$ 分。

样例解释 2

前 $2$ 轮的分数为 $100,100$。如果第 $3$ 轮取得 $0$ 分，则分数升序排列为 $S=(0,100,100)$，最终结果为 $100$。注意，最大分数 $100$ 有多个，但只去除其中一个（最小分数同理）。可以证明，为了使最终结果不少于 $100$，第 $3$ 轮至少需要取得 $0$ 分。

样例解释 3

前 $4$ 轮的分数为 $0,0,99,99$。可以证明，无论第 $5$ 轮取得多少分，最终结果都无法达到 $200$。

由 ChatGPT 4.1 翻译