← 返回题目列表

AtCoder · awc0022_b

B. 测试目标分数

中文机器翻译题面 查看原题

分数: 233 分

问题陈述

高桥参加了期末考试 N 科目。在每个科目中 i (1 \leq i \leq N),高桥得分 A_i 点。

在高桥的学校,如果有一门科目的分数低于目标分数 T 点,学生必须参加补课。

幸运的是,这所学校有“额外作业制度”。对于提交的每一份额外作业,高桥可以选择任意一个科目,并将该科目的分数增加 1 分。同一主题可以多次选择。每个科目的分数没有上限。但是,可以提交的额外作业总数最多为 M。也允许完全不提交额外的作业。

高桥希望通过策略性地提交额外作业来避免补课,以便所有科目的分数至少达到 T 点。

确定是否可以达到至少 T 在所有科目中总共提交最多 M 额外作业。如果可能,输出所需额外作业的最少数量。如果所有科目的分数至少为 T,输出 0。如果不可能,则输出 -1.

约束

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^9
  • 0 \leq T \leq 100
  • 0 \leq A_i \leq 100 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N M T
A_1 A_2 \ldots A_N
  • 第一行包含三个空格分隔的整数: N 代表科目数量, M 代表可以提交的额外作业的最大数量,以及 T 代表目标分数。
  • 第二行包含空格分隔的整数 A_1, A_2, \ldots, A_N 代表高桥在每个科目中获得的分数。

输出

如果有可能达到至少 T 在所有科目中,在一行中输出所需额外作业的最少数量。如果不可能,则输出 -1 在一行上。


示例输入 1

3 5 60
55 70 58

示例输出 1

-1

示例输入 2

5 10 80
75 80 90 60 85

示例输出 2

-1

示例输入 3

10 1000000000 70
65 70 72 68 55 80 90 45 70 71

示例输出 3

47