비즈니스 미팅

면접 대비

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

요약

각 회의의 가능한 기분 범위와 기분 변화가 주어질 때, 시작 기분 k에서 출발해 참석할 수 있는 회의를 가장 많이 고르고 그 순서를 출력합니다.

문제

알렉세이는 성공한 사업가이다. 하루 동안 여러 사업 파트너와 많은 미팅을 한다. 미팅은 종류가 다양해서 모두가 그를 즐겁게 하거나 기분을 좋게 만들지는 않는다. 기분이 너무 나쁘거나 너무 좋은 상태로 참석하면 알렉세이가 원하는 결과가 나오지 않는 미팅도 있다.

알렉세이는 최근 기분을 정수로 평가하는 법을 익혔다. 그는 각 미팅마다 참석이 가능한 최소 기분과 최대 기분을 정했고, 미팅이 끝난 뒤 기분이 어떻게 바뀌는지도 정했다. 이제 그는 하루 동안 미팅을 가능한 한 많이 하도록 순서를 정하려고 한다.

여러분의 과제는 모든 미팅 정보와 하루 시작 시점의 알렉세이 기분을 바탕으로, 미팅 수가 최대가 되는 순서를 찾는 프로그램을 작성하는 것이다.

첫 줄에 두 정수 $n$ 과 $k$ ( $1 \le n \le 20$ , $-100 \le k \le 100$ )가 주어진다. $n$ 은 미팅의 수이고, $k$ 는 하루 시작 시점의 알렉세이 기분이다.

다음 $n$ 개 줄에는 각각 세 정수 $a_i$ , $b_i$ , $c_i$ ( $-100 \le a_i, b_i, c_i \le 100$ )가 주어진다. 차례대로 미팅이 가능한 최소 기분, 최대 기분, 미팅이 끝난 뒤의 기분 변화량이다.

첫 줄에 가능한 최대 미팅 수 $m$ 을 출력한다. 다음 줄에는 미팅을 진행하는 순서대로 미팅 번호 $m$ 개를 출력한다. 미팅 번호는 입력에 주어진 순서대로 매긴다.

미팅 수가 최대가 되는 순서가 여러 개이면 그중 아무거나 출력한다.