В один замечательный день в компанию «X» завезли k автоматов. И не простых автоматов, а автоматов-программистов! Это был последний неудачный шаг перед переходом на андроидов-программистов, но это уже совсем другая история.
В компании сейчас n задач, для каждой из которых известно время начала ее выполнения si, длительность ее выполнения ti и прибыль компании от ее завершения ci. Любой автомат может выполнять любую задачу, ровно одну в один момент времени. Если автомат начал выполнять задачу, то он занят все моменты времени с si по si + ti - 1 включительно и не может переключиться на другую задачу.
Вам требуется выбрать набор задач, которые можно выполнить с помощью этих k автоматов и который принесет максимальную суммарную прибыль.
Выходные данные
Выведите n целых чисел x1, x2, ..., xn. Число xi должно быть равно 1, если задачу i следует выполнить, и 0 в противном случае.
Если оптимальных решений несколько, то выведите любое из них.
Примечание
В первом примере задания требуют выполнения в моменты времени 2 ... 8, 1 ... 3 и 4 ... 4, соответственно. Первое задание пересекается со вторым и третьим, поэтому можно выполнять либо его одно (прибыль 5), либо второе и третье (прибыль 6).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
2 7 5
1 3 3
4 1 3
|
0 1 1
|
|
2
|
5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1
|
1 1 0 0 1
|