Overview

This is a problem where you determine whether each quest satisfies the “efficiency condition” \(R_i \ge K \times D_i\), then sum up the experience points \(R_i\) of those that satisfy it and check whether the total is at least \(T\).

Analysis

The key point is that in this problem, there is no need to optimize “which quests to choose.” Takahashi has already decided to clear all and only the efficient quests, so there are only two things to do:

1. For each quest, check whether the condition \(R_i \ge K \times D_i\) is satisfied
2. Sum up \(R_i\) of the quests that satisfy the condition, and determine whether the total is at least \(T\)

Even with a straightforward approach, a full scan (examining all \(N\) quests sequentially) is sufficient. However, since the constraint is as large as \(N \le 2 \times 10^5\), unnecessary operations (such as sorting, DP, combinatorial search, etc.) would slow things down or make the implementation heavier. This problem can be solved in a single pass, so it can be handled with just a loop of \(N\) iterations.

Additionally, once the total experience reaches \(T\) or more, there is no need to read further. By outputting Yes and terminating midway, you can further reduce execution time (early termination).

Concrete examples: - If \(K=3\) and a quest has \((D,R)=(4,12)\), then \(12 \ge 3 \times 4\), so it qualifies for clearing - If \((D,R)=(5,14)\), then \(14 \not\ge 15\), so it does not qualify We just sum up the \(R\) values of qualifying quests and check whether the total reaches \(T\).

Algorithm

1. Read \(N, K, T\) from input
2. Initialize total = 0
3. For \(i=1..N\), repeat the following:
   • Read \(D_i, R_i\)
   • If \(R_i \ge K \times D_i\), then total += R_i
   • If total >= T, output Yes and terminate (early termination)
4. After the loop ends, output Yes if total >= T, otherwise output No

Complexity

• Time complexity: \(O(N)\) (just checking each quest once)
• Space complexity: \(O(1)\) (only a constant number of variables such as the running total)

Implementation Notes

• Since \(T \le 10^{18}\) can be very large, the total can also become large. However, Python integers do not overflow, so this is safe (in other languages, use 64-bit integers).

• Since the input can have up to \(2 \times 10^5\) lines, reading with sys.stdin.buffer.read() for fast input is recommended for stability.

• By returning Yes the moment total >= T is reached, you can speed things up in average cases.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    K = int(next(it))
    T = int(next(it))

    total = 0
    for _ in range(N):
        D = int(next(it))
        R = int(next(it))
        if R >= K * D:
            total += R
            if total >= T:
                print("Yes")
                return
    print("Yes" if total >= T else "No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.