Overview

Given \(N\) quests, select only those where the experience gained \(R_i\) is at least \(K\) times the stamina cost \(D_i\), and determine whether the total experience from the selected quests meets or exceeds the target value \(T\).

Analysis

The key insight of this problem is that the criterion for deciding which quests to complete is independent for each quest.

For each quest, we only need to individually check whether the condition \(R_i \geq K \times D_i\) is satisfied — the selection of other quests has no effect. Therefore, the problem can be solved with the following steps:

1. Prepare a variable to hold the total experience.
2. Examine each of the \(N\) quests one by one.
3. If a quest satisfies the condition, add its experience to the total.
4. Finally, check whether the total is at least \(T\).

As a note of caution, the target experience \(T\) can be as large as \(10^{18}\). Depending on the programming language, you may need to use a 64-bit integer type (such as long long in C++). However, in Python, the standard integer type can handle values of this magnitude, so there is no concern about overflow.

Algorithm

The implementation follows these steps:

1. Read \(N, K, T\) from the input.
2. Initialize a variable total_experience to \(0\) to store the total experience.
3. Loop \(N\) times, reading \(D_i, R_i\) for each quest.
4. Check efficiency using the condition if r >= k * d:.
5. If the condition is satisfied, add \(R_i\) to total_experience.
6. After the loop, output Yes if total_experience >= t, otherwise output No.

Complexity

• Time complexity: \(O(N)\)
  • Since we loop through each of the \(N\) quests once to make the determination, the processing finishes in linear time. This is sufficiently fast even when \(N = 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • The given code uses sys.stdin.read().split() to read all input at once as a list, consuming memory proportional to the input size.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), using sys.stdin.read().split() or sys.stdin.readline instead of repeatedly calling input() can reduce execution time.

• Condition expression: By directly translating the condition \(R_i \geq K \times D_i\) from the problem statement into code, we can make an exact determination using only integers without resorting to floating-point arithmetic (division).

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース・改行で分割する
    data = sys.stdin.read().split()
    if not data:
        return
    
    # イテレータを使用してデータを順番に処理する
    it = iter(data)
    
    # N: クエスト数, K: 効率の基準, T: 目標経験値
    try:
        n_str = next(it)
        k_str = next(it)
        t_str = next(it)
    except StopIteration:
        return

    n = int(n_str)
    k = int(k_str)
    t = int(t_str)
    
    total_experience = 0
    
    # 各クエストの情報を処理
    for _ in range(n):
        try:
            d = int(next(it))
            r = int(next(it))
            
            # 効率の良いクエスト（Ri >= K * Di）のみ経験値を加算
            if r >= k * d:
                total_experience += r
        except StopIteration:
            break
            
    # 合計経験値が目標 T 以上かどうかを判定
    if total_experience >= t:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.