Overview

This problem asks you to determine whether you can fully repay \(N\) debts—each growing due to interest every turn—using a fixed budget of \(P\) yen received each turn. Since each debt has a clear repayment deadline (the latest turn by which it must be repaid), we can compute these deadlines and apply a greedy algorithm (processing in order of earliest deadline) to solve the problem.

---

Analysis

1. Determining the “Repayment Deadline” for Each Debt

For a given debt \(i\), the remaining balance at the repayment phase of turn \(t\) (\(t \geq 1\)) is the initial balance \(H_i\) plus \(t-1\) applications of interest \(G_i\). That is, the balance is expressed as:

\[H_i + (t - 1) \times G_i\]

To fully repay this debt at turn \(t\), the balance at that point must be at most \(P\).

\[H_i + (t - 1) \times G_i \leq P\]

Let’s solve this inequality for \(t\).

\[(t - 1) \times G_i \leq P - H_i\]

\[t - 1 \leq \frac{P - H_i}{G_i}\]

\[t \leq \frac{P - H_i}{G_i} + 1\]

Since \(t\) must be an integer, the maximum turn \(T_i\) by which debt \(i\) can be repaid is expressed using floor division (\(\lfloor \rfloor\)) as:

\[T_i = \lfloor \frac{P - H_i}{G_i} \rfloor + 1\]

However, if the initial balance already exceeds the budget (\(P < H_i\)), the debt cannot be repaid even on turn \(1\). In this case, we set the repayment deadline to turn \(0\) (= impossible to repay).

2. In What Order Should We Repay?

Once we have computed the repayment deadline \(T_i\) for all debts, the next challenge is the constraint that “at most one debt can be repaid per turn.”

This is a classic task scheduling problem, and the optimal strategy is the greedy approach of “processing tasks in order of earliest deadline.” It is most efficient to prioritize tasks with the least slack and postpone those with later deadlines.

3. Determining Whether Full Repayment Is Possible

Let \(L\) be the list of all repayment deadlines sorted in ascending order. The \(j\)-th debt in the sorted list (0-indexed, i.e., \(0 \leq j < N\)) must be repaid by at least turn \(j + 1\). This is because at least \(j\) turns have been spent repaying the debts before it.

Therefore, if the following condition holds for all \(j\), then all debts can be fully repaid:

\[L[j] \geq j + 1\]

Conversely, if there exists any \(j\) such that \(L[j] < j + 1\), then that debt cannot be repaid by its deadline, and the answer is No.

---

Algorithm

1. For each debt \(i\) (\(1 \leq i \leq N\)), compute the repayment deadline \(T_i\) and append it to the list L.
   • If \(P < H_i\): \(T_i = 0\)
   • If \(P \geq H_i\): \(T_i = (P - H_i) // G_i + 1\) (// denotes floor division)
2. Sort the list L in ascending order.
3. For each \(j\) (\(0 \leq j < N\)), check whether L[j] < j + 1.
   • If any such element is found, output No and terminate.
4. If all elements satisfy the condition, output Yes.

---

Complexity

• Time Complexity: \(O(N \log N)\) Computing the repayment deadline for each debt takes \(O(N)\), sorting the list takes \(O(N \log N)\), and the final verification loop takes \(O(N)\). The overall bottleneck is the sorting step, which runs sufficiently fast (a few milliseconds to tens of milliseconds) for the constraint \(N \leq 2 \times 10^5\).

• Space Complexity: \(O(N)\) We use \(O(N)\) memory for the list L that stores the repayment deadline of each debt.

---

Implementation Notes

• Handling floor division: In Python, using the // operator automatically gives the integer result with the fractional part truncated (the floor function \(\lfloor \rfloor\)).

• Index correspondence: Since arrays in programming languages typically start from 0 (0-indexed), the deadline check for the \(j\)-th element (0-indexed) after sorting is compared against turn j + 1. Be careful about this off-by-one difference.

  Source Code

import sys


def solve():
    # 高速な入力処理
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    P = int(data[1])

    L = []
    idx = 2
    for _ in range(N):
        H = int(data[idx])
        G = int(data[idx + 1])
        idx += 2
        if P < H:
            L.append(0)
        else:
            L.append((P - H) // G + 1)

    # 昇順にソート
    L.sort()

    # 各jに対して、L[j]がj+1以上であるか確認
    for j in range(N):
        if L[j] < j + 1:
            print("No")
            return

    print("Yes")


if __name__ == "__main__":
    solve()

---

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