Overview

Since sweets of different types must be packed into separate boxes, we can independently calculate the number of boxes needed for each type and sum them up. For the \(i\)-th type, the total number of sweets is \(A_i + B_i\), and the minimum number of boxes needed when each box holds at most \(K\) sweets is \(\lceil (A_i + B_i)/K \rceil\).

Analysis

The key point of this problem is that sweets of different types cannot be placed in the same box.

In other words,

• How many boxes to use for sweets of type 1
• How many boxes to use for sweets of type 2
• …
• How many boxes to use for sweets of type \(N\)

can be considered completely independently. Saving boxes for one type never has a positive effect on another type.

---

Considering a single type

Let the total number of sweets of the \(i\)-th type be

\(C_i = A_i + B_i\)

Since there is no distinction between Takahashi’s and Aoki’s sweets, it suffices to look at just the total count.

Each box can hold at most \(K\) sweets, so the minimum number of boxes needed to pack all sweets of this type is

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

For example, if \(K = 5\) and \(C_i = 13\), then:

• Box 1: 5 sweets
• Box 2: 5 sweets
• Box 3: 3 sweets

So the number of boxes needed is \(3\). This matches

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

---

Why this is the minimum

Each box can hold at most \(K\) sweets. Therefore, to transport \(C_i\) sweets, at least

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

boxes are needed.

On the other hand, by actually “packing \(K\) sweets per box as much as possible and putting the remainder in the last box,” we can always pack them using exactly this many boxes. Thus, this is the minimum.

---

Why a naive approach doesn’t work

For example, if we consider a method like “simulating by placing sweets one by one into boxes,” since \(A_i, B_i\) can be up to \(10^9\), this would be far too slow.

However, in reality, all we need for each type is the total count \(A_i + B_i\). Therefore, by computing

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

for each type and summing them up, we finish with just \(N\) calculations.

---

How to write ceiling division

To compute

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

using only integers, the following expression is commonly used in Python:

Integer division of \(\frac{x + K - 1}{K}\)

In code:

(x + K - 1) // K

When \(A_i + B_i = 0\):

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

So the condition “no boxes are needed for this type” is naturally satisfied.

Algorithm

1. Initialize a variable ans representing the answer to 0.
2. For each type, do the following:
   • Read \(A_i, B_i\)
   • Compute the total count \(C_i = A_i + B_i\)
   • Calculate the required number of boxes \(\left\lceil \frac{C_i}{K} \right\rceil\) as (C_i + K - 1) // K
   • Add it to ans
3. Output ans at the end.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Since there is no distinction between Takahashi’s and Aoki’s sweets of the same type, it suffices to look at just A + B each time.

• Ceiling division can be written as (x + K - 1) // K.

• The answer can become large, but since Python’s integers automatically handle arbitrarily large values, there is no concern.

  Source Code

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

---

This editorial was generated by gpt-5.4-high.