Деловые встречи

시간 제한2초메모리 제한1024 MB

요약

각 회의의 허용 기분 범위를 지키며 최대 개수의 회의를 골라 순서를 정하는 문제로, n은 20 이하이다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Алексей --- успешный предприниматель и в течении одного дня у него бывает много встреч с разными деловыми партнерами. К сожалению, встречи бывают разные и не все приносят ему радость и после них настроение улучшается. Также, на многие встречи не стоит приходить в слишком плохом или хорошем настроении --- результат таких встреч может быть не таким, какой хочется Алексею.

К счастью, недавно Алексей научился оценивать свое настроение с помощью целых чисел. После этого для каждой встречи он оценил при каком максимальном и минимальном настроении стоит на нее приходить, а также как изменится его настроение после этой встречи. Теперь он хочет распланировать порядок встреч так, чтобы в течении дня совершить максимальное число встреч.

Ваша задача --- написать программу, которая по информации о всех встречах и настроении Алексея в начале дня находит порядок проведения встреч такой, что их количество при этом максимально.

입력

Первая строка входного файла содержит два целых числа $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$ целых чисел --- номера встреч в порядке их проведения. Встречи пронумерованы в порядке описания во входном файле.

Если ответов с максимальным числом встреч несколько, выведите любой.

예제2

예제 1
입력
```
3 0
1 3 3
0 1 2
1 3 1
```
예상 출력
```
3
2 3 1
```
예제 2
입력
```
3 1
-10 -5 3
-5 5 -2
-3 2 1
```
예상 출력
```
2
3 2
```