概要

各科目の点数が目標点 \(T\) に届いていない分を合計し、その合計が追加課題の上限 \(M\) 以下なら達成可能（最小必要数＝その合計）、超えるなら不可能として -1 を出力します。

考察

• 追加課題 1 つで「任意の 1 科目を 1 点上げられる」ので、ある科目 \(i\) の点数 \(A_i\) が \(T\) 未満なら、その科目だけで最低でも \(T-A_i\) 個の追加課題が必要です。
  逆に、\(A_i \ge T\) の科目には追加課題を使う必要がありません。
• したがって、全科目で必要な追加課題数の最小値は
  [ \sum_{i=1}^{N} \max(0,\,T-A_i) ] に一致します。これより少ない回数では、どこかの科目が必ず \(T\) に届きません。
• 素朴に「どの科目に課題を割り当てるか」をシミュレーションしたり、毎回最小の点数を探して上げるような実装をすると、無駄に複雑になったり、場合によっては \(M\) が最大 \(10^9\) なので「課題を 1 個ずつ」処理して TLE になる可能性があります。
• 本問では「不足分の合計」を一度計算するだけで十分です。これが \(M\) 以下なら可能、超えるなら不可能です。

具体例： - \(T=70\)、点数が \([65, 80, 69]\) のとき、不足分は \(5, 0, 1\) なので合計 \(6\)。
\(M \ge 6\) なら最小必要数は \(6\)、\(M < 6\) なら不可能です。

アルゴリズム

1. 変数 need = 0 を用意する。
2. 各科目の点数 \(A_i\) について、
   • もし \(A_i < T\) なら need += (T - A_i) を加算する。
3. 最後に need <= M なら need を出力し、そうでなければ -1 を出力する。

この need が「必要な追加課題の最小個数」そのものです。

計算量

• 時間計算量: \(O(N)\)（全科目を 1 回ずつ見るだけ）
• 空間計算量: \(O(1)\)（入力を逐次処理する想定で追加領域は定数）

実装のポイント

• \(N\) が最大 \(10^5\) なので、Python では sys.stdin.read() などでまとめて読み込み、ループで処理すると安定します。

• 合計 need は最大で \(N \times 100 \le 10^7\) 程度ですが、一般に大きくなり得るので整数型（Python の int）で問題ありません。

• \(T=0\) のようなケースでは不足分は常に 0 になり、答えは 0（追加課題不要）になります。

  ソースコード

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    T = int(next(it))
    need = 0
    for _ in range(N):
        a = int(next(it))
        if a < T:
            need += T - a
    print(need if need <= M else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。