B - テストの目標点 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は N 科目の期末テストを受けました。各科目 i（1 \leq i \leq N）において、高橋君は A_i 点を獲得しました。

高橋君の学校では、点数が目標点 T 点未満の科目が 1 科目でもあると、補習を受けなければなりません。

幸いなことに、この学校には「追加課題制度」があります。追加課題を 1 つ提出するごとに、好きな 1 科目を選んでその科目の点数を 1 点上げることができます。同じ科目を何度選んでもかまいません。また、各科目の点数に上限はありません。ただし、提出できる追加課題の数は合計で M 個以下です。追加課題を 1 つも提出しないことも許されます。

高橋君は、追加課題をうまく提出することで、すべての科目の点数を T 点以上にして補習を回避したいと考えています。

合計 M 個以下の追加課題の提出により、すべての科目で T 点以上を達成することが可能かどうかを判定してください。可能な場合は、そのために必要な追加課題の最小個数を出力してください。すでにすべての科目が 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
  • 1 行目には、科目数を表す整数 N 、提出できる追加課題の個数の上限を表す整数 M 、目標点を表す整数 T が、スペース区切りで与えられる。
  • 2 行目には、各科目で高橋君が獲得した点数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべての科目で T 点以上を達成することが可能な場合は、必要な追加課題の最小個数を 1 行で出力してください。不可能な場合は -1 を 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

Score : 233 pts

Problem Statement

Takahashi took final exams in N subjects. In each subject i (1 \leq i \leq N), Takahashi scored A_i points.

At Takahashi's school, if there is even one subject where the score is below the target score of T points, the student must attend supplementary lessons.

Fortunately, this school has an "extra assignment system." For each extra assignment submitted, Takahashi can choose any one subject and increase that subject's score by 1 point. The same subject may be chosen multiple times. There is no upper limit on the score for each subject. However, the total number of extra assignments that can be submitted is at most M. It is also allowed to submit no extra assignments at all.

Takahashi wants to avoid supplementary lessons by strategically submitting extra assignments so that all subjects' scores become at least T points.

Determine whether it is possible to achieve a score of at least T in all subjects by submitting a total of at most M extra assignments. If it is possible, output the minimum number of extra assignments needed. If all subjects already have scores of at least T, output 0. If it is impossible, output -1.

Constraints

  • 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)
  • All input values are integers.

Input

N M T
A_1 A_2 \ldots A_N
  • The first line contains three space-separated integers: N representing the number of subjects, M representing the maximum number of extra assignments that can be submitted, and T representing the target score.
  • The second line contains space-separated integers A_1, A_2, \ldots, A_N representing the scores Takahashi obtained in each subject.

Output

If it is possible to achieve a score of at least T in all subjects, output the minimum number of extra assignments needed on a single line. If it is impossible, output -1 on a single line.

Sample Input 1

3 5 60
55 70 58

Sample Output 1

-1

Sample Input 2

5 10 80
75 80 90 60 85

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

47