Overview

Each smartphone’s battery “decreases by a fixed amount per second and does not go below 0,” so we can directly compute the remaining battery at time \(T\) using a formula and sum it across all devices.

Analysis

Since smartphone \(i\)’s battery decreases by \(B_i\) mAh per second, a naive calculation suggests that at time \(T\), the remaining battery would be
\(A_i - B_i \times T\).

However, as stated in the problem, once the battery reaches \(0\), the phone powers off and the battery doesn’t decrease further (it never becomes negative).
Therefore, the actual remaining battery is:

• If \(A_i - B_iT > 0\): it remains \(A_i - B_iT\)
• If \(A_i - B_iT \le 0\): it is \(0\)

In other words, the remaining battery is \(\max(0, A_i - B_iT)\).

If we naively “simulate second by second,” since \(T\) can be up to \(10^9\), the complexity becomes \(O(NT)\), which is far too slow (TLE).
In this problem, we only need the value at time \(T\), so it suffices to look at each device once and compute it using the formula.

Example: When \(A=10, B=3, T=4\),
\(A-BT = 10-12 = -2\), but since it cannot be negative, the remaining battery is \(0\).

Algorithm

1. Initialize total = 0.
2. For each smartphone:
   • Compute rem = A_i - B_i * T
   • If rem > 0, add total += rem (otherwise, don’t add anything — equivalent to adding 0)
3. Output total.

This directly computes \(\sum_{i=1}^{N} \max(0, A_i - B_iT)\).

Complexity

• Time complexity: \(O(N)\) (each smartphone is processed once)
• Space complexity: \(O(1)\) (only a constant number of variables such as the total)

Implementation Notes

• B_i * T can be as large as \(10^9 \times 10^9 = 10^{18}\). Python’s int has arbitrary precision, so this is not an issue (in other languages, use 64-bit integers).

• You could also use max(0, rem), but in the code, we achieve the same effect by only adding when rem > 0.

• Since the input can have up to \(2 \times 10^5\) lines, using sys.stdin.buffer.readline for fast input is a safe choice.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, T = map(int, input().split())
    total = 0
    for _ in range(N):
        A, B = map(int, input().split())
        rem = A - B * T
        if rem > 0:
            total += rem
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.