概要

種類ごとにお菓子を別々の箱に詰めるしかないので、各種類について必要な箱数を独立に求めて足し合わせればよい問題です。
\(i\) 番目の種類の合計個数 \(A_i + B_i\) を、1箱あたり最大 \(K\) 個ずつ入れるときの最小箱数は \(\lceil (A_i + B_i)/K \rceil\) になります。

考察

この問題で重要なのは、異なる種類のお菓子を同じ箱に入れられないことです。

つまり、

• 1種類目のお菓子を何箱使うか
• 2種類目のお菓子を何箱使うか
• …
• \(N\) 種類目のお菓子を何箱使うか

は、それぞれ完全に独立に考えられます。
ある種類で箱を節約した結果が、別の種類に良い影響を与えることはありません。

---

1種類だけを考える

\(i\) 番目の種類のお菓子の合計を

\(C_i = A_i + B_i\)

とします。
高橋君のものと青木君のものに区別はないので、単に合計個数だけ見れば十分です。

1箱には最大 \(K\) 個まで入れられるので、この種類のお菓子を全部詰めるのに必要な最小箱数は

\(\left\lceil \frac{C_i}{K} \right\rceil\)

です。

例えば \(K = 5\)、\(C_i = 13\) なら、

• 1箱目に 5 個
• 2箱目に 5 個
• 3箱目に 3 個

と詰めればよいので、必要な箱数は \(3\) 個です。
これは

\(\left\lceil \frac{13}{5} \right\rceil = 3\)

と一致します。

---

なぜこれで最小なのか

1箱に入れられるのは多くても \(K\) 個です。
したがって、\(C_i\) 個のお菓子を運ぶには少なくとも

\(\left\lceil \frac{C_i}{K} \right\rceil\)

箱必要です。

一方で、実際に「できるだけ \(K\) 個ずつ詰めて、最後だけ余りを入れる」ことで、この個数の箱で必ず詰められます。
よってこれが最小です。

---

素朴な方法がダメな理由

例えば、「1個ずつ箱に入れてシミュレーションする」ような方法を考えると、\(A_i, B_i\) は最大 \(10^9\) なので到底間に合いません。

しかし実際には、必要なのは各種類の合計個数 \(A_i + B_i\) だけです。
そのため、種類ごとに

\(\left\lceil \frac{A_i + B_i}{K} \right\rceil\)

を計算して足せば、\(N\) 回の計算だけで終わります。

---

切り上げ除算の書き方

整数だけで

\(\left\lceil \frac{x}{K} \right\rceil\)

を求めるには、Python では次の式がよく使われます。

\(\frac{x + K - 1}{K}\) の整数除算

コードでは

(x + K - 1) // K

です。

\(A_i + B_i = 0\) のときも、

(0 + K - 1) // K = 0

となるので、「その種類のために箱は不要」という条件も自然に満たせます。

アルゴリズム

1. 答えを表す変数 ans を 0 で初期化する。
2. 各種類について以下を行う。
   • \(A_i, B_i\) を読む
   • 合計個数 \(C_i = A_i + B_i\) を求める
   • 必要箱数 \(\left\lceil \frac{C_i}{K} \right\rceil\) を
     (C_i + K - 1) // K で計算する
   • それを ans に加える
3. 最後に ans を出力する。

計算量

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

実装のポイント

• 同じ種類のお菓子では高橋君と青木君の区別はないので、毎回 A + B だけ見れば十分です。

• 切り上げ除算は (x + K - 1) // K で書けます。

• 答えは大きくなる可能性がありますが、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())
        ans += (A + B + K - 1) // K
    print(ans)

if __name__ == "__main__":
    main()

---

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