C. Програм бичдэг төхөөрөмж

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн гайхалтай өдөр $X$ компани $k$ ширхэг төхөөрөмжтэй болжээ. Эдгээр нь энгийн нэгэн төхөөрөмж биш байсан бөгөөд програм бичдэг машинууд байжээ!

Компанид нийт $n$ ширхэг ажил байсан бөгөөд ажил болгоны эхлэх хугацаа $s_{i}$, үүний үргэлжлэх хугацаа $t_{i}$, ажил болгоноос компаний олох ашиг $c_{i}$. Аль ч машин нэгэн зэрэг нэг ажлыг л хийж чадна. Хэрвээ машин ажлыг гүйцэтгэж эхэлсэн тохиолдолд энэ машин $s_{i}$-ээс $s_{i} + t_{i} - 1$ хугацааны хооронд завгүй байх (хоёр хязгаарын хугацаанууд орно) бөгөөд ажлыг нь дундаас нь өөрчлөх боломжгүй.

Таны даалгавар бол компани хамгийн их ашиг олсон байхаар эдгээр $k$ ширхэг машинд ажлуудыг хуваарилж өгөх явдал юм.

Оролт

Эхний мөрөнд ажлын болон машины тоо болох $n$, $k$ ($1 ≤ n ≤ 1000$, $1 ≤ k ≤ 50$) бүхэл тоонууд өгөгдөнө.

Дараагийн $n$ ширхэг мөрөнд зайгаар тусгаарлагдсан $3$ ширхэг бүхэл тоо $s_{i}, t_{i}, c_{i}$ ($1 ≤ s_{i}, t_{i} ≤ 10^{9}$, $1 ≤ c_{i} ≤ 10^{6}$) өгөгдөнө. Үүнд $s_{i}$ нь $i$ дэхь даалгаврын эхлэх хугацаа, $t_{i}$ нь $i$ дэхь даалгаврын үргэлжлэх хугацаа, $c_{i}$ нь $i$ дэхь даалгавраас олох ашиг.

Гаралт

$n$ ширхэг бүхэл тоог $x_{1}, x_{2}, ..., x_{n}$ хэвлэнэ үү. Хэрвээ $i$ дэхь даалгавар хийгдэх ёстой бол $x_{i}$-н утга $1$, харин хийгдэх ёсгүй бол $0$-тэй тэнцүү байна.

Хэрвээ олон хариу байвал аль нэгийг нь хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
3 1
2 7 5
1 3 3
4 1 3
Гаралт
0 1 1
Оролт
5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1
Гаралт
1 1 0 0 1

Тэмдэглэл

Эхний жишээнд ажлуудыг хугацааны $2-8$, $1-3$, $4-4$ завсаруудад хийх ёстой. Эхний ажлын хугацаа $2$ дахь болон $3$ дахь даалгавруудтай давхцаж байгаа учраас бид нэг бол эхний ажлыг (ашиг $5$), эсвэл $2$ болон $3$ дахь (ашиг $6$) ажлыг машинд даалгана.

Сэтгэгдлүүдийг ачааллаж байна...