/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は RPG ゲームを遊んでいます。このゲームには N 個のクエストがあり、i 番目のクエスト (1 \leq i \leq N) には消費スタミナ D_i と獲得経験値 R_i が設定されています。各クエストはクリアしないか、1回だけクリアするかのいずれかを選べます。
高橋君は「効率の良いクエストだけをクリアする」というプレイスタイルを持っています。高橋君にとって効率の良いクエストとは、獲得経験値が消費スタミナの K 倍以上であるクエスト、すなわち R_i \geq K \times D_i を満たすクエストのことです。ここで K は高橋君が定めた効率の基準倍率です。
高橋君はこのプレイスタイルに従い、効率の良いクエストをすべてクリアし、それ以外のクエストは一切クリアしません。
高橋君がこのプレイスタイルに従ったとき、クリアしたクエストから得られる獲得経験値の合計が目標経験値 T 以上になるかどうかを判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 100
- 1 \leq T \leq 10^{18}
- 1 \leq D_i \leq 10^4
- 1 \leq R_i \leq 10^9
- 入力はすべて整数
入力
N K T D_1 R_1 D_2 R_2 \vdots D_N R_N
- 1 行目には、クエストの数 N 、効率の基準倍率 K 、目標経験値 T が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各クエストの情報が与えられる。
- 1 + i 行目には、i 番目のクエストの消費スタミナ D_i と獲得経験値 R_i が、スペース区切りで与えられる。
出力
高橋君が効率の良いクエストをすべてクリアしたとき、獲得経験値の合計が目標経験値 T 以上になるならば Yes を、そうでなければ No を出力せよ。
入力例 1
3 2 100 10 30 5 15 8 20
出力例 1
No
入力例 2
5 3 500 20 100 15 45 10 50 25 80 30 150
出力例 2
No
入力例 3
8 5 1000000000 100 600 200 1000 500 2500 1000 5000 300 1000 150 900 400 2000 250 1500
出力例 3
No
Score : 233 pts
Problem Statement
Takahashi is playing an RPG game. The game has N quests, and the i-th quest (1 \leq i \leq N) has a stamina cost of D_i and an experience reward of R_i. For each quest, he can choose either not to clear it or to clear it exactly once.
Takahashi has a playstyle of "only clearing efficient quests." For Takahashi, an efficient quest is one whose experience reward is at least K times its stamina cost, that is, a quest satisfying R_i \geq K \times D_i. Here, K is the efficiency threshold multiplier set by Takahashi.
Following this playstyle, Takahashi clears all efficient quests and does not clear any other quests.
Determine whether the total experience gained from the quests Takahashi clears following this playstyle is at least the target experience T.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 100
- 1 \leq T \leq 10^{18}
- 1 \leq D_i \leq 10^4
- 1 \leq R_i \leq 10^9
- All inputs are integers
Input
N K T D_1 R_1 D_2 R_2 \vdots D_N R_N
- The first line contains the number of quests N, the efficiency threshold multiplier K, and the target experience T, separated by spaces.
- From the 2nd line to the (N + 1)-th line, the information for each quest is given.
- The (1 + i)-th line contains the stamina cost D_i and the experience reward R_i of the i-th quest, separated by spaces.
Output
If the total experience gained when Takahashi clears all efficient quests is at least the target experience T, print Yes; otherwise, print No.
Sample Input 1
3 2 100 10 30 5 15 8 20
Sample Output 1
No
Sample Input 2
5 3 500 20 100 15 45 10 50 25 80 30 150
Sample Output 2
No
Sample Input 3
8 5 1000000000 100 600 200 1000 500 2500 1000 5000 300 1000 150 900 400 2000 250 1500
Sample Output 3
No