概要

各スマートフォンのバッテリーは「毎秒一定量減り、0未満にはならない」ので、時刻 \(T\) の残量を式で直接求めて全台分を合計します。

考察

スマートフォン \(i\) のバッテリー残量は、毎秒 \(B_i\) mAh ずつ減るため、単純に考えると時刻 \(T\) では
\(A_i - B_i \times T\) だけ残っていそうです。

ただし問題文の通り、残量が \(0\) になったら電源が切れてそれ以上減りません（負の値にならない）。
よって実際の残量は

• \(A_i - B_iT > 0\) のとき：そのまま \(A_i - B_iT\)
• \(A_i - B_iT \le 0\) のとき：\(0\)

つまり、残量は \( \max(0, A_i - B_iT)\) です。

素朴に「1 秒ずつシミュレーション」すると、\(T\) が最大 \(10^9\) なので \(O(NT)\) となり到底間に合いません（TLE）。
この問題は 時刻 \(T\) の値が欲しいだけなので、各端末を1回ずつ見て式で計算すれば十分です。

例：\(A=10, B=3, T=4\) のとき
\(A-BT = 10-12 = -2\) ですが、負にはならないので残量は \(0\) です。

アルゴリズム

1. 合計 total = 0 を用意する。
2. 各スマートフォンについて：
   • rem = A_i - B_i * T を計算
   • rem > 0 なら total += rem（そうでなければ加算しない＝0を足すのと同じ）
3. total を出力する。

これは \( \sum_{i=1}^{N} \max(0, A_i - B_iT)\) をそのまま計算しています。

計算量

• 時間計算量: \(O(N)\)（各スマホを1回ずつ計算）
• 空間計算量: \(O(1)\)（合計など定数個の変数のみ）

実装のポイント

• B_i * T は最大で \(10^9 \times 10^9 = 10^{18}\) になり得ます。Python の int は任意精度なので問題ありません（他言語では 64-bit 整数を使う）。

• max(0, rem) でもよいですが、コードでは rem > 0 のときだけ足すことで同じ処理をしています。

• 入力が最大 \(2 \times 10^5\) 行あるため、高速入力として sys.stdin.buffer.readline を使うと安全です。

  ソースコード

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

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