A8385. Machine Programming

One remarkable day company "X" received $k$ machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story.

The company has now $n$ tasks, for each of them we know the start time of its execution $s_{i}$ , the duration of its execution $t_{i}$ , and the company profit from its completion $c_{i}$ . Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from $s_{i}$ to $s_{i}+t_{i}-1$ , inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these $k$ machines, and which will bring the maximum total profit.

The first line contains two integer numbers $n$ and $k$ ( $1<=n<=1000$ , $1<=k<=50$ ) — the numbers of tasks and machines, correspondingly.

The next $n$ lines contain space-separated groups of three integers $s_{i},t_{i},c_{i}$ ( $1<=s_{i},t_{i}<=10^{9}$ , $1<=c_{i}<=10^{6}$ ), $s_{i}$ is the time where they start executing the $i$ -th task, $t_{i}$ is the duration of the $i$ -th task and $c_{i}$ is the profit of its execution.

Print $n$ integers $x_{1},x_{2},...,x_{n}$ . Number $x_{i}$ should equal $1$ , if task $i$ should be completed and otherwise it should equal $0$ .

If there are several optimal solutions, print any of them.

In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).