Overview

This problem asks us to find the minimum number of times \(K\) the speaker must be played so that the required volume reaches all booths arranged in a straight line.

We efficiently find the minimum \(K\) that satisfies the conditions using binary search, by appropriately choosing the speaker’s installation position \(P\).

---

Analysis

1. Naive Approach and Its Limitations

If we try to search over both the speaker’s installation position \(P\) and the number of times \(K\), there are up to \(10^9\) candidates for \(P\), and \(K\) can reach up to \(10^{18}\), making brute force (TLE) or simulation impossible.

Therefore, we reformulate the problem as a decision problem: “Given a fixed \(K\), does there exist an installation position \(P\) that satisfies the conditions?”

2. Prerequisites for Speaker Placement

To deliver sound to all booths, the distance from the speaker to each booth must be less than \(V\) (i.e., at most \(V - 1\)). If the distance is \(V\) or more, the delivered volume becomes \(0\) regardless of how many times the speaker is played.

Therefore, if the distance between the leftmost booth coordinate \(min\_X\) and the rightmost booth coordinate \(max\_X\) is greater than \(2V - 2\), it is impossible to deliver sound to all booths no matter how \(P\) is chosen. In this case, we can immediately output -1 and terminate before performing any search.

\[max\_X - min\_X \ge 2V - 1 \implies \text{impossible (-1)}\]

3. Conditions on Position \(P\) for a Fixed Number of Times \(K\)

When the number of times \(K\) is fixed, the condition for delivering sound to booth \(i\) is:

\[K \times \max(V - |X_i - P|, 0) \ge D_i\]

Since \(D_i \ge 1\) and \(K \ge 1\), we need \(\max(V - |X_i - P|, 0) > 0\). Therefore, removing the absolute value and rearranging:

\[V - |X_i - P| \ge \left\lceil \frac{D_i}{K} \right\rceil\]

\[|X_i - P| \le V - \left\lceil \frac{D_i}{K} \right\rceil\]

Solving this for \(P\), we obtain the range in which \(P\) must lie to satisfy the condition for booth \(i\):

\[X_i - V + \left\lceil \frac{D_i}{K} \right\rceil \le P \le X_i + V - \left\lceil \frac{D_i}{K} \right\rceil\]

If the intersection of these \(P\) ranges across all booths \(i\) is non-empty, then that \(K\) is achievable. Specifically, if we compute the maximum of the lower bounds \(max\_L\) and the minimum of the upper bounds \(min\_R\) from each booth, a valid \(P\) exists if and only if:

\[max\_L \le min\_R\]

4. Applying Binary Search

The decision problem “Does there exist a \(P\) satisfying the conditions with \(K\) times?” has monotonicity — as \(K\) increases, the conditions become more relaxed (the allowable range of \(P\) widens), so if it’s possible for some \(K\), it’s also possible for any larger \(K\). Therefore, we can perform binary search on the value of \(K\).

---

Algorithm

1. Initial Check:

   • Find the minimum coordinate \(min\_X\) and maximum coordinate \(max\_X\) among all booths.
   • If \(max\_X - min\_X \ge 2V - 1\), output -1.

2. Determining the Search Range:

   • low (lower bound): The minimum number of times needed even if the speaker is placed directly above a booth (distance 0). $\(\text{low} = \max_{1 \le i \le N} \left\lceil \frac{D_i}{V} \right\rceil\)$
   • high (upper bound): The number of times needed to deliver sound to all booths when the speaker is tentatively placed at position \(P = \lfloor (min\_X + max\_X) / 2 \rfloor\).

3. Binary Search:

   • Set mid = (low + high) // 2.
   • Determine in \(O(N)\) whether there exists a \(P\) satisfying the conditions with mid times.
     • For each booth \(i\), compute \(req_i = \lceil D_i / mid \rceil\).
     • \(L_i = X_i - V + req_i\)
     • \(R_i = X_i + V - req_i\)
     • Update \(max\_L = \max(L_i)\) and \(min\_R = \min(R_i)\).
     • If at any point \(max\_L > min\_R\), we can immediately determine it’s impossible and break out of the loop.
   • If the judgment is “possible”, search for an even smaller \(K\) by setting high = mid - 1 and updating the answer candidate.
   • If the judgment is “impossible”, a larger \(K\) is needed, so set low = mid + 1.

---

Complexity

• Time Complexity: \(O(N \log (\text{high} - \text{low}))\)

  • The decision procedure in the binary search performs \(O(1)\) computation for each booth \(N\) times, so each iteration takes \(O(N)\).
  • Since \(D_i \le 10^{18}\), the width of the search range is at most around \(10^{18}\). The number of binary search iterations is \(\log_2(10^{18}) \approx 60\).
  • Therefore, the overall complexity is approximately \(60 \times N\), which is well within the time limit.

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used to store the coordinates and hearing thresholds of each booth.

---

Implementation Notes

1. Ceiling Division with Integer Arithmetic

In programming, the ceiling division \(\lceil A / B \rceil\) for positive integers \(A, B\) can be computed using only integer arithmetic as follows, avoiding floating-point precision issues:

(A + B - 1) // B

2. Optimizing the Search Range

While setting the upper bound high to an extremely large value like \(10^{18}\) would still produce correct results, by using “the number of times needed assuming placement at a position near the center \(P\)” as the initial value of high (as done in the code), we can narrow the binary search range and further reduce execution time.

Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    V = int(data[1])
    
    XD = []
    idx = 2
    for _ in range(N):
        XD.append((int(data[idx]), int(data[idx+1])))
        idx += 2
        
    min_X = XD[0][0]
    max_X = XD[0][0]
    for x, _ in XD:
        if x < min_X:
            min_X = x
        if x > max_X:
            max_X = x
            
    if max_X - min_X >= 2 * V - 1:
        print(-1)
        return

    # K の下限 (low) の計算
    low = 1
    for _, d in XD:
        val = (d + V - 1) // V
        if val > low:
            low = val
            
    # K の上限 (high) の計算
    # P を (min_X + max_X) // 2 に置いたときに必要な K を上限とする
    P = (min_X + max_X) // 2
    high = 1
    for x, d in XD:
        dist = abs(x - P)
        val = (d + V - dist - 1) // (V - dist)
        if val > high:
            high = val
            
    # 二分探索
    ans = high
    while low <= high:
        mid = (low + high) // 2
        possible = True
        max_L = -10**18
        min_R = 10**18
        for x, d in XD:
            req = (d + mid - 1) // mid
            L = x - V + req
            if L > max_L:
                max_L = L
            R = x + V - req
            if R < min_R:
                min_R = R
            if max_L > min_R:
                possible = False
                break
        if possible:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.