Preemptive Task Scheduling on Multiple Processors

We are given (n) tasks, numbered from (1) to (n). For each task (i), there are three parameters (p_i, c_i, k_i), which represent the following:

- The task can start no earlier than time (p_i).
- The task requires (c_i) units of processing time.
- The task must be completed by time (k_i).

There are (m) processors available. A processor can run only one task at any given time, and a task can be processed on only one processor at a time. However, the processing of a task may be interrupted arbitrarily and can resume (even on a different processor) later.

The problem is to decide if there exists a scheduling strategy such that all tasks complete within their allowed time windows. A necessary and sufficient condition is that for every time interval ([t_1, t_2]), the total amount of processing that must be done during that interval does not exceed (m\times (t_2-t_1)). More formally, for each interval ([t_1, t_2]), if the required amount of processing that must occur in that interval is defined as
[ R(t_1,t_2) = \sum_{i=1}^{n} \max\Bigl{0,; c_i - \max(0, t_1-p_i) - \max(0, k_i-t_2)\Bigr}, ]
then a feasible schedule exists if and only if [ R(t_1,t_2) \le m\times (t_2-t_1) \quad \text{for all } t_1,t_2 \text{ with } t_1<t_2. ]
This condition can be checked by considering all candidate time points (release times and deadlines).

inputFormat

The first line contains two integers (n) and (m) denoting the number of tasks and the number of processors, respectively. Each of the next (n) lines contains three numbers: (p_i), (c_i), and (k_i), where (p_i) is the earliest start time for task (i), (c_i) is the processing time required by task (i), and (k_i) is the deadline by which task (i) must be finished.

outputFormat

Output a single line with either "YES" if it is possible to schedule all tasks so that they meet their deadlines, or "NO" otherwise.

sample

2 1
1 1 2
2 1 3

YES