题目描述

题目译自 PA 2016 Runda 5 Szeregowanie zadań

Bajtazar 正在庆祝他的十三岁生日。为此，他从父母那里收到了一台新电脑。寿星毫不犹豫地撕开纸箱，拿起包装内的一本小册子。原来，这台电脑有 $m$ 个处理器。Bajtazar 对这个事实感到非常高兴——他终于可以同时执行多个任务了。

故事的发展没有让他久等。片刻之后，男孩已经准备了一份包含 $n$ 个任务（编号从 $1$ 到 $n$）的列表，计划在新电脑上执行这些任务。任务编号为 $i$ 的任务需要 $c_{i}$ 秒来完成，最早可以在打开礼物后 $p_{i}$ 秒开始执行，并且必须在打开礼物后 $k_{i}$ 秒之前完成。每个任务可以被多次中断，并在不同处理器之间转移执行，但不能同时在两个或多个处理器上执行。任务转移所需的时间可以忽略不计。是否存在一种任务调度方式（包括任务中断和处理器间转移的策略），可以让 Bajtazar 按时完成所有计划的任务？

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 100)$，分别表示需要执行的任务数量和处理器数量。

接下来的 $n$ 行描述各个任务。第 $i$ 行描述任务编号 $i$，包含三个整数 $p_{i}, k_{i}, c_{i}$ $(0 \leq p_{i} < k_{i} \leq 10^{6}, 1 \leq c_{i} \leq k_{i} - p_{i})$，分别表示可以执行任务的时间区间起点和终点（从打开礼物开始计算的秒数）以及执行任务所需的时间。

输出格式

输出一行，若存在一种任务调度方式可以按时完成所有任务输出 TAK，否则输出 NIE。

3 2
3 8 3
2 5 2
3 7 3

TAK

2 1
0 1 1
0 1 1

NIE