概要

各植物について、\(D\) 日後の高さは「現在の高さ \(A_i\) + 1日あたりの成長量 \(B_i \times D\)」で求められます。
これを全植物分足し合わせれば答えになります。

考察

重要な観察は、植物ごとに成長が独立であり、しかも成長量が毎日一定であることです。
したがって \(i\) 番目の植物の \(D\) 日後の高さは次の1行で表せます：

\( A_i + B_i \cdot D \)

求めたいのはその総和なので、

\( \sum_{i=1}^{N} (A_i + B_i \cdot D) \)

をそのまま計算すればよいです。

---

素朴に「1日ずつシミュレーション」すると、各日ごとに全植物を更新する必要があり、計算量は \(O(ND)\) になります。
制約では \(N \le 10^5,\ D \le 10^6\) なので、最悪 \(10^{11}\) 回程度の操作になり現実的ではありません（TLE）。

ここで、毎日更新する代わりに まとめて \(D\) 日分を一気に加算 すれば、各植物につき1回の計算で済み、\(O(N)\) で解けます。

アルゴリズム

1. \(N, D\) を読む。
2. 合計値 total を 0 で初期化。
3. 各植物について \((A, B)\) を読み、total += A + B * D を行う。
4. total を出力。

例えば \(D=3\)、ある植物が \((A,B)=(10,2)\) なら、3日後は \(10+2\times3=16\) です。
これを全植物に対して同様に処理して足し合わせます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を保持せずその場で加算）

実装のポイント

• Python では整数が多倍長なので、制約内の大きな値（最大で \(2\times10^{16}\) 程度）も安全に扱えます。

• 入力行数が多いため、input() より高速な sys.stdin.readline を使う実装は有効です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    total = 0
    for _ in range(N):
        A, B = map(int, input().split())
        total += A + B * D
    print(total)

if __name__ == "__main__":
    main()

---

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