창던지기 놀이

산술 대학교에서는 가끔 산술 수업이 취소된다. 취소된 수업 시간에 학생들을 바쁘게 하려고 학장은 던지기용 표적과 창을 파는 기계를 구입했다.

표적은 여러 겹의 층으로 되어 있다. 창 하나는 여러 층을 뚫을 수 있다. 목표는 모든 층을 뚫는 것이다.

각 창은 지름, 세기, 비용을 가진다. 기계는 정해진 순서대로 창을 제안한다. 제안받은 창은 구매해서 바로 던지거나 버릴 수 있다. 어느 쪽이든 기계는 다음 창을 제안한다. 모든 창을 제안하고 나면 기계는 꺼진다.

처음 던진 창은 자기 지름과 같은 지름, 자기 세기와 같은 깊이의 둥근 구멍을 만든다. 이후에 던지는 창은 모두 구멍의 중심에 맞는다. 마지막으로 던진 창의 지름이 지금까지 던진 모든 창의 지름을 넘지 않으면, 아직 뚫리지 않은 첫 번째 층부터 층을 뚫는다. 그렇지 않으면 지름이 이 창의 지름보다 작은 구멍이 있는 층 중 가장 깊은 층부터 뚫는다.

각 창은 세기만큼의 층을 뚫는다. 어떤 창이 뚫는 층은 지름이 더 작은 창이 뚫은 층에 따라 달라지지 않는다. 창의 세기가 마지막 층을 뚫기에 충분하면 창이 표적을 관통하고 던지기가 끝난다.

기계가 제안하는 창 중에서 모든 층을 뚫으면서 비용의 합이 최소가 되도록 살 창을 고르시오.

첫 줄에 정수 $n$과 $m$이 주어진다. $n$은 창의 개수, $m$은 표적 층의 개수이다 ($1 \leq n, m \leq 2000$).

이어지는 $n$개의 줄에 창 하나의 정보가 세 정수 $d_i$, $s_i$, $c_i$로 주어진다. 각각 창의 지름, 세기, 비용이다 ($1 \leq d_i, c_i \leq 10^9$, $1 \leq s_i \leq 2000$). 창은 기계가 제안하는 순서대로 주어진다.

첫 줄에 총 비용 $c$와 선택한 창의 개수 $k$를 출력한다. 둘째 줄에는 선택한 창의 번호를 증가하는 순서로 $k$개 출력한다. 번호는 기계가 제안한 순서를 따른다.

모든 층을 뚫을 수 없으면 $-1$을 출력한다. 최적해가 여러 개이면 그중 아무거나 출력한다.