#2498. Cutoff

Cutoff

[ABC321B] Cutoff

题面翻译

nn 场比赛,目标总分为 mm,其中前 n1n-1 场的分数为 a1,a2an1a_1,a_2\dots a_{n-1}

总分的计算方法为 nn 场比赛去掉得分最高和最低的两场后,剩余分数之和。

问第 nn 场最少需要得多少分,才能使总分大于等于目标总分,一场比赛的分数取值为 [0,100][0,100],若无法达到,输出 -1

题目描述

以下の手順で行われる試験があります。

  • 試験は 1 1 ラウンド目から N N ラウンド目までの N N ラウンドからなる。
  • 各ラウンドに対し、 0 0 以上 100 100 以下の整数でスコアが与えられる。
  • N N ラウンドのスコアのうち、最高スコアと最低スコアを除いた N2 N-2 ラウンドのスコアの合計が最終結果となる。
    • 厳密には、各ラウンドのスコアを昇順に並べた列を S=(S1,S2,,SN) S=(S_1,S_2,\dots,S_N) としたとき、最終結果は S2+S3++SN1 S_2+S_3+\dots+S_{N-1} となる。

現在、試験のうち N1 N-1 ラウンドが終了し、 i i ラウンド目のスコアは Ai A_i でした。 最終結果を X X 以上とするために N N ラウンド目に取るべきスコアの最小値を出力してください。 但し、 N N ラウンド目にどのようなスコアを取っても最終結果が X X 以上にならない場合、代わりに -1 と出力してください。 なお、 N N ラウンド目に取りうるスコアは 0 0 以上 100 100 以下の整数であることに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N X X A1 A_1 A2 A_2 \dots AN1 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  N  100 3\ \le\ N\ \le\ 100
  • 0  X  100 × (N2) 0\ \le\ X\ \le\ 100\ \times\ (N-2)
  • 0  Ai  100 0\ \le\ A_i\ \le\ 100

Sample Explanation 1

4 4 ラウンド目までのスコアは 40,60,80,50 40,60,80,50 でした。 5 5 ラウンド目にスコア 70 70 を取ると、スコアを昇順に並べた列は S=(40,50,60,70,80) S=(40,50,60,70,80) となり、最終結果は 50+60+70=180 50+60+70=180 となります。 なお、最終結果を 180 180 以上にするために取るべきスコアの最小値が 70 70 であることが示せます。

Sample Explanation 2

2 2 ラウンド目までのスコアは 100,100 100,100 でした。 3 3 ラウンド目にスコア 0 0 を取ると、スコアを昇順に並べた列は S=(0,100,100) S=(0,100,100) となり、最終結果は 100 100 となります。 最大スコアである 100 100 が複数ありますが、そのうち 1 1 つしか除かれないことに注意してください。(最小スコアについても同様です) なお、最終結果を 100 100 以上にするために取るべきスコアの最小値が 0 0 であることが示せます。

Sample Explanation 3

4 4 ラウンド目までのスコアは 0,0,99,99 0,0,99,99 でした。 5 5 ラウンド目にどのようなスコアを取っても、最終結果を 200 200 以上にすることができないことが示せます。