题目背景

译自 Potyczki Algorytmiczne 2016 R5 Szeregowanie zadań [B] (SZE)。

题目描述

有 $n$ 个任务，编号 $1\sim n$。任务 $i$ 有三个参数 $p_i,c_i,k_i$，含义为：

• 这个任务必须在时刻 $p_i$（或者 $p_i$ 之后）开始执行；
• 这个任务需要 $c_i$ 单位时间；（意思是，它需要在处理器上运行的总时间为 $c_i$）
• 这个任务必须在时刻 $k_i$（或者 $k_i$ 之前）完成。

有 $m$ 个处理器用来执行任务。

一个处理器同一时间只能处理一个任务，一个任务同一时间只能在一个处理器上被处理。每个任务可以在处理时被中断任意次，可以在任意时刻（不一定是整数时刻）被中断，在中断后可以分配给另一个处理器处理。

是否存在一种策略可以满足所有要求？

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行三个整数 $p_i,k_i,c_i$，描述一个任务。

输出格式

如果存在，输出一行一个 $\texttt{TAK}$；否则输出一行一个 $\texttt{NIE}$。

3 2
3 8 3
2 5 2
3 7 3

TAK

2 1
0 1 1
0 1 1

NIE

提示

• $1\le n,m\le 100$；
• $0\le p_i\lt k_i\le 10^6$；
• $1\le c_i\le k_i-p_i$。