Overview

Since each of the \(N\) debts has a “last turn by which it can be repaid (deadline),” this problem asks us to determine whether all debts can be scheduled for repayment within their deadlines.

Analysis

Relationship Between Turns and Balances

Consider turns as \(0\)-indexed. At the start of the repayment phase on turn \(t\), the balance of debt \(i\) is:

\[H_i + t \cdot G_i\]

(It starts at \(H_i\) on turn \(0\), becomes \(H_i + G_i\) on turn \(1\), and so on, increasing over time.)

Finding the “Deadline” for Each Debt

The condition for being able to repay debt \(i\) on turn \(t\) is \(H_i + t \cdot G_i \leq P\). Rearranging this gives:

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

In other words, the last turn on which debt \(i\) can be repaid (its deadline) is \(T_i = \lfloor (P - H_i) / G_i \rfloor\).

• If \(H_i > P\), then the debt is already impossible to repay even at turn \(0\) (the balance only keeps increasing), so immediately output No.

Reduction to a Scheduling Problem

At most \(1\) debt can be repaid per turn, and each debt \(i\) must be repaid on one of the turns \(0, 1, \ldots, T_i\).

This is equivalent to the classic scheduling problem: “Given \(N\) jobs each with a deadline \(T_i\), where only \(1\) job can be processed at each time slot, can all jobs be completed within their deadlines?”

Greedy Determination

There is a well-known method for solving this problem:

Sort by deadline in ascending order. If the deadline of the \(j\)-th job (\(0\)-indexed) is at least \(j\), then a feasible schedule exists.

Intuitive reasoning: We assign jobs in order of earliest deadline to the earliest available turn. The \(j\)-th job can be assigned to turn \(j\) at the earliest, so if \(T_j < j\), it is impossible. Conversely, if all jobs satisfy \(T_j \geq j\), then assigning the \(j\)-th job to turn \(j\) always yields a valid schedule.

Algorithm

1. For each debt \(i\), if \(H_i > P\), output No and terminate.
2. Compute the deadline \(T_i = \lfloor (P - H_i) / G_i \rfloor\).
3. Sort the \(T_i\) values in ascending order.
4. Scan the sorted array: if the \(j\)-th value (\(0\)-indexed) is less than \(j\), output No; if all pass, output Yes.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck)
• Space complexity: \(O(N)\) (for storing the deadline array)

Implementation Notes

• By checking \(H_i \leq P\) first, we guarantee that \((P - H_i)\) is non-negative before performing the division.

• Since \(G_i \geq 1\) is guaranteed by the constraints, there is no concern about division by zero.

• Values are at most around \(10^9\), so overflow is not a concern, though care may be needed depending on the language.

• Concrete example: When \(P = 10, H = [5, 8, 3], G = [2, 3, 4]\), the deadlines are \(\lfloor 5/2 \rfloor = 2, \lfloor 2/3 \rfloor = 0, \lfloor 7/4 \rfloor = 1\). After sorting: \([0, 1, 2]\). For each \(j\), \(T_j \geq j\) holds (\(0 \geq 0, 1 \geq 1, 2 \geq 2\)), so the answer is Yes.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = int(input_data[idx]); idx += 1
    
    debts = []
    for i in range(N):
        H = int(input_data[idx]); idx += 1
        G = int(input_data[idx]); idx += 1
        debts.append((H, G))
    
    # At turn t (0-indexed), a debt i has balance H_i + t * G_i
    # We can pay it at turn t if H_i + t * G_i <= P, i.e., t <= (P - H_i) / G_i
    # If H_i > P and G_i > 0, we can never pay it (unless G_i = 0... but G_i >= 1)
    # Actually if H_i > P, then even at t=0, H_i + 0*G_i = H_i > P, and it only grows, so impossible.
    
    # We need to assign each debt to a distinct turn, and at that turn the balance must be <= P.
    # Each debt i can be paid at turns 0, 1, ..., T_i where T_i = floor((P - H_i) / G_i) if H_i <= P, else impossible.
    
    # This is a bipartite matching / scheduling problem:
    # Each debt has a deadline T_i (last turn it can be paid), and we need to schedule N debts
    # on N distinct turns. This is feasible iff when we sort by deadline, each debt i (0-indexed after sorting)
    # has deadline >= i.
    
    # This is the classic "scheduling with deadlines" greedy: sort by deadline ascending,
    # and check that the j-th job (0-indexed) has deadline >= j.
    
    deadlines = []
    for H, G in debts:
        if H > P:
            print("No")
            return
        # max turn (0-indexed) at which we can pay: floor((P - H) / G)
        T = (P - H) // G
        deadlines.append(T)
    
    deadlines.sort()
    
    for j in range(N):
        if deadlines[j] < j:
            print("No")
            return
    
    print("Yes")

solve()

---

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