Overview

For each project, determine whether the allocated budget \(A_i\) exceeds the appropriate budget \(B_i\), and find the number of such cases along with the total excess amount \(\sum (A_i - B_i)\).

Analysis

The key observation is the following single point:

• A refund is required only when \(A_i > B_i\), and the refund amount is exactly \(A_i - B_i\).

Therefore, we simply process each row independently: - If \(A_i > B_i\), increment the count by \(+1\) - Add \((A_i - B_i)\) to the total refund amount

That’s all there is to it.
There are no dependencies between projects, and no sorting or complex data structures are needed.

Even with a straightforward approach, since \(N \le 2 \times 10^5\), an \(O(N)\) solution is more than sufficient. However, in Python, repeatedly calling input() with large input can be slow. Therefore, it is safer to read all input at once using fast input (sys.stdin.buffer.read()).

Examples: - \((A, B) = (120, 100)\): over budget, refund amount is \(20\) - \((A, B) = (80, 100)\): no refund needed (\(A \le B\))

In this way, we check all projects and tally up the count and total.

Algorithm

1. Read \(N\).
2. Initialize cnt = 0 (number of over-budget projects) and total = 0 (total refund amount).
3. For \(i = 1\) to \(N\):
   • Read \(A_i, B_i\)
   • If \(A_i > B_i\):
     • cnt += 1
     • total += A_i - B_i
4. Output cnt and total.

Complexity

• Time complexity: \(O(N)\) (each project is examined exactly once)
• Space complexity: \(O(1)\) (only aggregation variables are needed. ※In implementations that read all input at once, the input data is stored, making it effectively \(O(N)\))

Implementation Notes

• Since \(N\) can be up to \(2 \times 10^5\), it is advisable to use fast input (sys.stdin.buffer.read().split()) in Python.

• The total total can be as large as approximately \(N \times 10^9\), but since Python integers do not overflow, this poses no problem.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    cnt = 0
    total = 0
    for _ in range(n):
        a = int(next(it))
        b = int(next(it))
        if a > b:
            cnt += 1
            total += a - b
    sys.stdout.write(f"{cnt} {total}")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.