Overview

Sum up the shortfall of each subject’s score from the target score \(T\), and if that total is within the additional assignment limit \(M\), achievement is possible (minimum required = that total); otherwise, output -1 to indicate it’s impossible.

Analysis

• Since one additional assignment can “raise any one subject’s score by 1 point,” if a subject \(i\) has score \(A_i\) less than \(T\), that subject alone requires at least \(T - A_i\) additional assignments.
  Conversely, subjects where \(A_i \ge T\) do not need any additional assignments.
• Therefore, the minimum number of additional assignments needed across all subjects is exactly
  [ \sum_{i=1}^{N} \max(0,\,T-A_i) ] With fewer than this number, at least one subject will inevitably fail to reach \(T\).
• If you naively simulate “which subject to assign each task to,” or implement an approach that finds and raises the minimum score each time, it becomes unnecessarily complex. In some cases, since \(M\) can be up to \(10^9\), processing “one assignment at a time” could result in TLE.
• In this problem, it suffices to compute the “total shortfall” once. If it is at most \(M\), it’s possible; if it exceeds \(M\), it’s impossible.

Concrete example: - When \(T=70\) and scores are \([65, 80, 69]\), the shortfalls are \(5, 0, 1\), totaling \(6\).
If \(M \ge 6\), the minimum required number is \(6\); if \(M < 6\), it’s impossible.

Algorithm

1. Prepare a variable need = 0.
2. For each subject’s score \(A_i\):
   • If \(A_i < T\), add need += (T - A_i).
3. Finally, if need <= M, output need; otherwise, output -1.

This need is exactly the “minimum number of additional assignments required.”

Complexity

• Time complexity: \(O(N)\) (just one pass through all subjects)
• Space complexity: \(O(1)\) (assuming input is processed sequentially, only constant extra space is needed)

Implementation Notes

• Since \(N\) can be up to \(10^5\), in Python it’s stable to read all input at once using sys.stdin.read() and process it in a loop.

• The total need is at most around \(N \times 100 \le 10^7\), but since it can generally be large, using an integer type (Python’s int) causes no issues.

• In cases like \(T=0\), the shortfall is always 0, and the answer is 0 (no additional assignments needed).

  Source Code

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()

This editorial was generated by gpt-5.2-high.