Overview

Given the stamina cost and experience points gained for each quest, the problem asks us to select “efficient quests” (experience gained \(\geq K \times\) stamina cost) and determine whether the total experience from those quests is at least the target value \(T\).

Analysis

In this problem, we need to individually determine whether each quest is “efficient” and sum up the experience points of all efficient quests.

The key observation is that an efficient quest is one that satisfies “\(R_i \geq K \times D_i\)”. This is a simple comparison, and no sorting or complex preprocessing is required.

A straightforward approach is to check the condition for every quest and add the experience points if it qualifies. Since each quest can be evaluated in constant time, this method is sufficiently fast.

Conversely, if the number of quests \(N\) were very large (e.g., \(10^6\) or more), a more advanced algorithm might be needed, but since \(N \leq 2 \times 10^5\) in this problem, a brute-force scan is fast enough.

Also, the total experience can be as large as \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\), so a 64-bit integer type (Python’s standard int) must be used instead of a 32-bit integer type.

Algorithm

1. For each quest \((D_i, R_i)\), determine whether \(R_i \geq K \times D_i\).
2. Sum up the experience points \(R_i\) of all quests that satisfy the condition.
3. If the final total is at least \(T\), output Yes; otherwise, output No.

For example, given the following input:

3 2 10
2 5
3 6
1 3

• Quest 1: \(5 \geq 2 \times 2 = 4\) → OK
• Quest 2: \(6 \geq 2 \times 3 = 6\) → OK
• Quest 3: \(3 \geq 2 \times 1 = 2\) → OK

Total experience = \(5 + 6 + 3 = 14 \geq 10\) → Output is Yes

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Since each quest is evaluated in constant time, the overall runtime is linear. Additionally, only a single variable is needed to maintain the running total, so the additional memory usage is constant.

Implementation Notes

• When reading input, managing each quest’s \((D_i, R_i)\) as a tuple or list makes the code easier to organize.

• The total should be handled with a 64-bit integer type (Python’s int handles this automatically).

• Make sure the inequality in the condition is written correctly (\(R_i \geq K \times D_i\)).

  Source Code

# 入力の受け取り
N, K, T = map(int, input().split())
quests = [tuple(map(int, input().split())) for _ in range(N)]

# 効率の良いクエストの経験値合計を計算
total_exp = 0
for D, R in quests:
    if R >= K * D:
        total_exp += R

# 目標達成可否の判定と出力
if total_exp >= T:
    print("Yes")
else:
    print("No")

---

This editorial was generated by qwen3-coder-480b.