決め打ち二分探索を行います。\(K\) を \(1\) つ定め、答えが \(K\) 以下となるか判定します。

各ブースに注目すると、\(K,V,X_i\) が固定値であるためある位置で聞こえる音量が \(D_i\) 以上となるような \(P\) の集合は区間となります。したがって、その区間を各ブースについてそれぞれ求め、\(N\) 個の区間の積集合が空集合かどうかで判定問題を解くことができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

n, v = map(int, input().split())
a = []
for i in range(n):
    x, d = map(int, input().split())
    a.append((x, d))
INF = 10**18 + 2026
ok, ng = INF, 0
while ok - ng != 1:
    vs = (ok + ng) // 2
    le = []
    ri = []
    for x, d in a:
        m = v - (d + vs - 1) // vs
        if m < 0:
            break
        le.append(x - m)
        ri.append(x + m)
    if len(le) != n:
        ng = vs
        continue
    if max(le) <= min(ri):
        ok = vs
    else:
        ng = vs
print(-1 if ok == INF else ok)