概要

各お菓子の種類ごとに、合計個数 \(A_i + B_i\) を「1箱に最大 \(K\) 個まで」という条件で分割したときの最小箱数を求め、それらを全種類分足し合わせれば答えになります。

考察

この問題の重要な点は、異なる種類を同じ箱に入れられないことです。
つまり、種類ごとの箱詰めは完全に独立しています。

\(i\) 番目の種類の合計を \( s_i = A_i + B_i \) とすると、この種類だけで必要な箱数は

• \(s_i = 0\) なら \(0\) 箱
• \(s_i > 0\) なら「\(K\) 個ずつ詰める」と最小になり、
  \( \left\lceil \frac{s_i}{K} \right\rceil \) 箱

です。

ここで素朴に「1箱ずつシミュレーションして \(K\) 個取り出す」をやると、個数が最大 \(10^9\) なので現実的ではありません（TLE）。
そこで、切り上げ除算を整数演算で一発計算します：

\( \left\lceil \frac{s}{K} \right\rceil = \frac{s+K-1}{K}\ (\text{整数除算}) \)

これを全種類に対して足し合わせればよいです。

具体例

\(K=5,\ s=12\) のとき
必要箱数は \(5,5,2\) の3箱なので \(3\)。
式でも \( (12+5-1)//5 = 16//5 = 3 \) で一致します。

アルゴリズム

1. \(N, K\) を読む。
2. 答え ans = 0 を用意。
3. 各種類について：
   • \(A, B\) を読む
   • \(s = A + B\) を計算
   • \(s > 0\) なら ans += (s + K - 1) // K
4. ans を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 切り上げ除算は math.ceil を使わず、(s + K - 1) // K で安全・高速に計算できます。

• s = 0 のときも上式は 0 になりますが、コードでは if s > 0 を入れて意図を明確にしています。

• 合計は大きくなる可能性がありますが、Python の整数は任意精度なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    ans = 0
    for _ in range(N):
        A, B = map(int, input().split())
        s = A + B
        if s > 0:
            ans += (s + K - 1) // K
    print(ans)

if __name__ == "__main__":
    main()

---

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