Phân công máy móc

Một công ty vừa nhận về $k$ cỗ máy giống hệt nhau và đang có $n$ công việc cần xử lý.

Công việc thứ $i$ bắt buộc phải bắt đầu đúng tại thời điểm $s_i$, kéo dài $t_i$ đơn vị thời gian, và mang lại lợi nhuận $c_i$ nếu được hoàn thành. Không được phép dời lịch bắt đầu của bất kỳ công việc nào.

Mỗi cỗ máy đều có thể làm bất kỳ công việc nào, nhưng tại mỗi thời điểm chỉ làm được đúng một công việc. Nếu một cỗ máy nhận công việc $i$, nó bận trong toàn bộ các thời điểm $s_i,s_i+1,\dots ,s_i+t_i-1$ và không thể chuyển sang công việc khác trong khoảng đó. Ngay tại thời điểm $s_i+t_i$ cỗ máy đã rảnh và có thể nhận công việc mới.

Công ty không bắt buộc phải làm hết tất cả công việc. Hãy chọn ra một tập công việc có thể thực hiện được bằng $k$ cỗ máy sao cho tổng lợi nhuận thu được là lớn nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: số công việc và số cỗ máy.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $s_i$, $t_i$, $c_i$: thời điểm bắt đầu, thời gian thực hiện và lợi nhuận của công việc thứ $i$.

Dữ liệu ra

In ra $n$ số nguyên $x_1,x_2,\dots ,x_n$, trong đó $x_i=1$ nếu công việc thứ $i$ được chọn và $x_i=0$ nếu ngược lại.

Nếu có nhiều cách chọn cùng đạt tổng lợi nhuận lớn nhất, in ra một cách bất kỳ.

Ràng buộc

• $1\le n\le 1000$
• $1\le k\le 50$
• $1\le s_i,t_i\le {10}^9$
• $1\le c_i\le {10}^6$

Ví dụ