atcoder#ABC183D. [ABC183D] Water Heater

[ABC183D] Water Heater

配点 : 400400

問題文

給湯器が 11 つあり、毎分 WW リットルのお湯を供給することができます。

NN 人の人がいます。ii 番目の人は時刻 SiS_i から TiT_i までの間 (時刻 TiT_i ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 PiP_i リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。

すべての人に計画通りにお湯を供給することはできますか?

制約

  • 1N2×1051\leq N \leq 2\times 10^5
  • 0Si<Ti2×1050\leq S_i < T_i \leq 2\times 10^5
  • 1W,Pi1091\leq W, P_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN WW

S1S_1 T1T_1 P1P_1

\vdots

SNS_N TNT_N PNP_N

出力

すべての人に計画通りにお湯を供給することができるなら Yesを、できないなら Noを出力せよ。

4 10
1 3 5
2 4 4
3 10 6
2 4 1
No

時刻 33 から 44 の間に、2,3,42,3,4 番目の人がそれぞれ 毎分 4,6,14,6,1 リットル、合計毎分 1111 リットルのお湯を使おうとしています。

給湯器は毎分 1010 リットルしかお湯を供給することができないので、計画通りに供給することはできません。

4 10
1 3 5
2 4 4
3 10 6
2 3 1
Yes
6 1000000000
0 200000 999999999
2 20 1
20 200 1
200 2000 1
2000 20000 1
20000 200000 1
Yes