Overview

For each type of candy, compute the total count \(A_i + B_i\) and determine the minimum number of boxes needed when splitting under the constraint of “at most \(K\) candies per box.” Summing these across all types gives the answer.

Reasoning

The key point of this problem is that different types cannot be placed in the same box.
In other words, the box-packing for each type is completely independent.

Let the total for the \(i\)-th type be \( s_i = A_i + B_i \) Then the number of boxes needed for this type alone is:

• If \(s_i = 0\), then \(0\) boxes
• If \(s_i > 0\), packing \(K\) candies per box is optimal, requiring
  \( \left\lceil \frac{s_i}{K} \right\rceil \) boxes

Here, naively simulating “taking out \(K\) candies one box at a time” is not practical since the count can be up to \(10^9\) (TLE).
Instead, we compute the ceiling division in a single integer operation:

\( \left\lceil \frac{s}{K} \right\rceil = \frac{s+K-1}{K}\ (\text{integer division}) \)

We simply sum this over all types.

Concrete Example

When \(K=5,\ s=12\):
The required boxes hold \(5, 5, 2\) candies respectively, so the answer is \(3\).
Using the formula: \( (12+5-1)//5 = 16//5 = 3 \) which matches.

Algorithm

1. Read \(N, K\).
2. Initialize the answer ans = 0.
3. For each type:
   • Read \(A, B\)
   • Compute \(s = A + B\)
   • If \(s > 0\), then ans += (s + K - 1) // K
4. Output ans.

Complexity

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

Implementation Notes

• Ceiling division is computed safely and efficiently using (s + K - 1) // K instead of math.ceil.

• When \(s = 0\), the formula also yields 0, but adding if s > 0 in the code makes the intent clearer.

• The total can become large, but since Python integers have arbitrary precision, there is no concern about overflow.

  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())
        s = A + B
        if s > 0:
            ans += (s + K - 1) // K
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.