#ABC183D. 热水器

热水器

AT_abc183_d [ABC183D] Water Heater

题目描述

\hspace{15pt}有 11 个热水器,每分钟可以提供 ww 升热水。

\hspace{15pt}现在来了 nn 个人想使用热水。第 ii 个人打算从时刻 sis_i 使用到时刻 tit_i(tit_i 除外),每分钟需要使用 pip_i 升热水。由于热水倒出来会迅速变冷,因此不能储存。

\hspace{15pt}你能按照他们的计划提供热水吗?

输入格式

\hspace{15pt}第一行输入两个整数 $n,w \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq w \leqq 10^9\right)$ 代表使用热水的人数与热水器每分钟可以提供的热水升数。

\hspace{15pt}此后 nn 行,第 ii 行输入三个整数 $s_i,t_i,p_i \left(0 \leqq s_i < t_i \leqq 2 \times 10^5;\ 1 \leqq p_i \leqq 10^9\right)$ 代表第 ii 个人使用热水的时间区间与每分钟需要的热水量。

输出格式

\hspace{15pt}如果可以按照计划为每个人提供热水,在一行上输出 "Yes"\texttt{"Yes"};否则,在一行上输出 "No"\texttt{"No"}。

测试样例

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

样例 1 解释

\hspace{15pt}在时刻 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