概要

各本について「読んだ回数 \(C_i\) が \(K\) 以下か」を判定し、条件を満たす本の満足度 \(D_i\) を合計する問題です。

考察

求めたいのは「\(C_i \le K\) の本をすべて選んだときの \(D_i\) の総和」なので、選び方の最適化や並べ替えは一切不要です。
各本は独立に判定でき、条件を満たせば加算、満たさなければ無視するだけで答えが出ます。

素朴にやるべきことは単純ですが、\(N \le 2 \times 10^5\) と大きいため、入力処理が遅い実装（例：毎回 input() を呼ぶ、余計なデータ構造に全て格納するなど）だと環境によっては時間が厳しくなることがあります。
そこで、入力をまとめて高速に読み込み、走査しながらその場で合計する方針にします（不要な保存をしない）。

例：
\(K=3\)、本が \((C,D)=(1,10),(5,7),(3,4)\) なら、条件を満たすのは \(C=1,3\) の本なので合計は \(10+4=14\) です。

アルゴリズム

1. \(N, K\) を読む
2. 合計 total = 0 を用意
3. \(i=1\) から \(N\) まで繰り返す
   
   • \((C_i, D_i)\) を読む
     
   • もし \(C_i \le K\) なら total += D_i
4. total を出力する
   （該当がなければ加算されず 0 のままなので、そのまま正しい）

計算量

• 時間計算量: \(O(N)\)（各本を1回ずつ確認するだけ）
• 空間計算量: \(O(1)\)（合計値など定数個の変数のみ）

実装のポイント

• Pythonでは高速入力のために sys.stdin.buffer.read().split() のようにまとめ読みすると安定します。

• 合計は最大で \(2 \times 10^{14}\) 程度になり得ますが、Pythonの int は多倍長なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    K = int(next(it))
    total = 0
    for _ in range(N):
        c = int(next(it))
        d = int(next(it))
        if c <= K:
            total += d
    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

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