Overview

This is a problem where you pack \(N\) types of sweets into boxes and need to find the total number of boxes by calculating the required number of boxes for each type.

Analysis

Key Observations

1. Different types of sweets cannot be placed in the same box, so we can consider each type independently. The number of boxes for one type does not affect how other types are packed.

2. For the same type, there is no distinction between Takahashi’s and Aoki’s sweets, so the \(i\)-th type of sweet can simply be treated as \(A_i + B_i\) items.

3. For each type, we pack a total of \(A_i + B_i\) sweets with at most \(K\) per box, so the required number of boxes can be found using ceiling division (the ceiling function).

Concrete Example

For example, if \(K = 3\) and there are \(7\) sweets of a certain type in total: - Box 1: 3 sweets - Box 2: 3 sweets - Box 3: 1 sweet

Therefore, \(\lceil 7 / 3 \rceil = 3\) boxes are needed.

If the total is \(0\), no boxes are needed, so we skip that type.

Comparison with a Naive Approach

Since this problem only requires computing independently for each type and summing up the results, no particularly complex algorithm is needed. However, since \(A_i + B_i\) can be up to \(2 \times 10^9\), you need to be careful about the range of 64-bit integers (in Python, integer overflow does not occur, so there is no need to worry).

Algorithm

1. Read \(N\) and \(K\).
2. Initialize a variable ans to \(0\) to store the answer.
3. For each type \(i\):
   • Compute \(\text{total} = A_i + B_i\).
   • If \(\text{total} > 0\), add \(\lceil \text{total} / K \rceil\) to ans.
4. Output ans.

The ceiling division \(\lceil a / b \rceil\) can be computed in Python using math.ceil(a / b) or (a + b - 1) // b.

Complexity

• Time complexity: \(O(N)\) — only constant-time computation is performed for each type
• Space complexity: \(O(1)\) — since input is read sequentially, almost no additional memory is needed

Implementation Notes

• Using math.ceil: Python’s math.ceil(total / K) may cause floating-point precision issues when total or K is large. A safer method that uses only integer arithmetic is (total + K - 1) // K. However, under the constraints of this problem (\(A_i + B_i \leq 2 \times 10^9\)), math.ceil also works correctly.

• Using sys.stdin.readline: Since \(N\) can be as large as \(2 \times 10^5\), we use sys.stdin.readline, which is faster than the standard input(), to read input.

• Skipping when the total is \(0\): When \(A_i = B_i = 0\), no boxes are needed, so we check total > 0 with a conditional branch (since math.ceil(0 / K) = 0, skipping is not strictly necessary for correctness, but we make it explicit).

  Source Code

import math
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    total = a + b
    if total > 0:
        ans += math.ceil(total / K)
print(ans)

---

This editorial was generated by claude4.6opus-thinking.