640. Air Conditioner
0
Medium
Gildong is the owner of a bulgogi restaurant. Due to the high number of customers, many of them prefer to make reservations before visiting. Gildong is dedicated to satisfying his customers and has even memorized their preferred temperature ranges. He wants to ensure customer satisfaction by controlling the temperature of the restaurant.
The restaurant has an air conditioner with three states: off, heating, and cooling. When the air conditioner is off, the temperature remains constant. When it's heating, the temperature increases by 1 degree per minute. When it's cooling, the temperature decreases by 1 degree per minute. Gildong can change the state of the air conditioner at any integer minute. The air conditioner is initially off.
Each customer has three values: ti - the time (in minutes) when the i-th customer visits the restaurant, li - the lower bound of their preferred temperature range, and hi - the upper bound of their preferred temperature range.
A customer is satisfied if the temperature at the time of their visit falls within their preferred range. Formally, the i-th customer is satisfied if and only if the temperature is between li and hi (inclusive) at the ti-th minute.
Given the initial temperature, the list of reserved customers' visit times, and their preferred temperature ranges, you need to determine if it's possible to satisfy all customers.
Input Format
The first line of the input contains two integers n and m (1≤n≤100, -10^9≤m≤10^9), where n is the number of reserved customers and m is the initial temperature of the restaurant.
Next, n lines follow. The i-th line contains three integers ti, li, and hi (1≤ti≤10^9, -10^9≤li≤hi≤10^9), representing the time when the i-th customer visits, the lower bound of their preferred temperature range, and the upper bound of their preferred temperature range, respectively. The preferred temperature ranges are inclusive.
The customers are given in non-decreasing order of their visit time, and the current time is 0.
Output Format
Print "YES" if it is possible to satisfy all customers. Otherwise, print "NO".
Example
Input
3 0
5 1 2
7 3 5
10 -1 0
Output
YES
Constraints
1 ≤ n ≤ 100
-10^9 ≤ m ≤ 10^9
1 ≤ t_i ≤ 10^9
-10^9 ≤ l_i ≤ 10^9
-10^9 ≤ h_i ≤ 10^9
-10^9 ≤ m ≤ 10^9
1 ≤ t_i ≤ 10^9
-10^9 ≤ l_i ≤ 10^9
-10^9 ≤ h_i ≤ 10^9
Loading...
View Submissions
Console