/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 件の借金を抱えています。
各借金 i（1 \leq i \leq N）には、初期残高 H_i 円と、毎ターン加算される固定の利息額 G_i 円が設定されています。
高橋君はこれらの借金をターン制で返済していきます。各ターンの開始時に、高橋君は P 円を受け取ります。この P 円はそのターン内でのみ使用でき、ターン終了時に未使用分は消滅します。
各ターンは以下の手順で進行します：
- 返済フェーズ：高橋君は、まだ完済していない借金の中から 1 件を選んで完済するか、何もしないかを選択します。ただし、選べるのはその時点での残高が P 以下である借金に限ります。借金を完済する場合、その借金の残高と同額を支払い、その借金は以後消滅します（残高が 0 になります）。P 円のうち支払いに使わなかった分はそのまま消滅し、次のターンには持ち越せません。部分的な返済（残高の一部だけを支払うこと）はできません。1 ターンに完済できるのは最大 1 件です。
- 利息フェーズ：返済フェーズの終了後、まだ完済されていない全ての借金 i について、残高がそれぞれ G_i 円増加します。
最初のターンの返済フェーズ開始時点において、各借金 i の残高は初期残高 H_i 円です。
高橋君が最適な順番で借金を返済するとき、有限回のターン内に全ての借金を完済できるかどうかを判定してください。完済できる場合は Yes を、できない場合は No を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^9
- 1 \leq H_i \leq 10^9
- 1 \leq G_i \leq 10^9
- 入力はすべて整数
入力
N P H_1 G_1 H_2 G_2 \vdots H_N G_N
- 1 行目には、借金の件数を表す整数 N と、高橋君が毎ターン受け取る金額を表す整数 P が、スペース区切りで与えられる。
- 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目の借金の初期残高 H_i と毎ターン加算される固定の利息額 G_i が、スペース区切りで与えられる。
出力
全ての借金を完済できる場合は Yes を、できない場合は No を 1 行で出力せよ。
入力例 1
3 10 6 2 2 1 8 1
出力例 1
Yes
入力例 2
3 10 9 2 10 1 3 1
出力例 2
No
入力例 3
10 100 80 5 70 10 95 1 40 15 10 10 60 4 99 1 50 8 30 7 20 20
出力例 3
Yes
入力例 4
25 1000000 851860 12345 1000000 99999 200008 33333 725932 45678 622226 22222 700000 150000 200000 40000 111115 98765 555556 111111 185185 54321 76000 42000 222223 777777 340000 60000 430000 30000 904947 13579 57000 41000 250000 250000 90000 65000 111120 88888 382720 123456 200008 44444 90000 70000 200008 99999 55000 45000 111120 55555
出力例 4
Yes
入力例 5
1 1000000000 1000000000 1000000000
出力例 5
Yes
Score : 400 pts
Problem Statement
Takahashi has N debts.
Each debt i (1 \leq i \leq N) has an initial balance of H_i yen and a fixed interest amount of G_i yen that is added every turn.
Takahashi repays these debts in a turn-based manner. At the beginning of each turn, Takahashi receives P yen. This P yen can only be used within that turn, and any unused portion disappears at the end of the turn.
Each turn proceeds as follows:
- Repayment Phase: Takahashi chooses one debt that has not yet been fully repaid and pays it off completely, or chooses to do nothing. However, he can only choose a debt whose current balance is at most P. When paying off a debt, he pays an amount equal to that debt's balance, and that debt disappears thereafter (its balance becomes 0). Any portion of the P yen not used for payment simply disappears and cannot be carried over to the next turn. Partial repayment (paying only a portion of the balance) is not allowed. At most 1 debt can be fully repaid per turn.
- Interest Phase: After the repayment phase ends, for every debt i that has not yet been fully repaid, its balance increases by G_i yen.
At the start of the repayment phase of the first turn, the balance of each debt i is the initial balance H_i yen.
Determine whether Takahashi can fully repay all debts within a finite number of turns if he repays them in the optimal order. If he can, output Yes; otherwise, output No.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^9
- 1 \leq H_i \leq 10^9
- 1 \leq G_i \leq 10^9
- All inputs are integers
Input
N P H_1 G_1 H_2 G_2 \vdots H_N G_N
- The first line contains an integer N representing the number of debts and an integer P representing the amount Takahashi receives each turn, separated by a space.
- The i-th of the following N lines (1 \leq i \leq N) contains the initial balance H_i and the fixed interest amount G_i added each turn for the i-th debt, separated by a space.
Output
If all debts can be fully repaid, output Yes; otherwise, output No on a single line.
Sample Input 1
3 10 6 2 2 1 8 1
Sample Output 1
Yes
Sample Input 2
3 10 9 2 10 1 3 1
Sample Output 2
No
Sample Input 3
10 100 80 5 70 10 95 1 40 15 10 10 60 4 99 1 50 8 30 7 20 20
Sample Output 3
Yes
Sample Input 4
25 1000000 851860 12345 1000000 99999 200008 33333 725932 45678 622226 22222 700000 150000 200000 40000 111115 98765 555556 111111 185185 54321 76000 42000 222223 777777 340000 60000 430000 30000 904947 13579 57000 41000 250000 250000 90000 65000 111120 88888 382720 123456 200008 44444 90000 70000 200008 99999 55000 45000 111120 55555
Sample Output 4
Yes
Sample Input 5
1 1000000000 1000000000 1000000000
Sample Output 5
Yes