| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 448 | 6 | 6 | 1.367% |
Алексей --- успешный предприниматель и в течении одного дня у него бывает много встреч с разными деловыми партнерами. К сожалению, встречи бывают разные и не все приносят ему радость и после них настроение улучшается. Также, на многие встречи не стоит приходить в слишком плохом или хорошем настроении --- результат таких встреч может быть не таким, какой хочется Алексею.
К счастью, недавно Алексей научился оценивать свое настроение с помощью целых чисел. После этого для каждой встречи он оценил при каком максимальном и минимальном настроении стоит на нее приходить, а также как изменится его настроение после этой встречи. Теперь он хочет распланировать порядок встреч так, чтобы в течении дня совершить максимальное число встреч.
Ваша задача --- написать программу, которая по информации о всех встречах и настроении Алексея в начале дня находит порядок проведения встреч такой, что их количество при этом максимально.
Первая строка входного файла содержит два целых числа $n$ и $k$ (1ドル \le n \le 20,ドル $-100 \le k \le 100$) --- количество встреч и настроение Алексея в начале дня.
Следующие $n$ строк содержат по три целых числа $a_i,ドル $b_i$ и $c_i$ ($-100 \le a_i, b_i, c_i \le 100$) --- минимальное, максимальное настроение при котором встреча возможна и изменение настроения по окончании встречи, соответственно.
В первой строке выходного файла выведите число $m$ --- максимально возможно число встреч. В следующей строке выведите $m$ целых чисел --- номера встреч в порядке их проведения. Встречи пронумерованы в порядке описания во входном файле.
Если ответов с максимальным числом встреч несколько, выведите любой.
3 0 1 3 3 0 1 2 1 3 1
3 2 3 1
3 1 -10 -5 3 -5 5 -2 -3 2 1
2 3 2