기차
시간 제한1초메모리 제한512 MB
각 승객의 승차역, 하차역, 요금이 주어질 때 선택한 모든 승객이 목적지에 도착하도록 승객을 고르고 탑승 순서를 정해 요금 합을 최대로 만드는 문제입니다.
문제
철도 회사가 객차 한 량에 좌석 N개를 둔 새 기차 시제품을 출시했다. 좌석은 기차 앞쪽부터 1번에서 N번까지 번호가 매겨져 한 줄로 늘어서 있다.
모든 승객은 다음 규칙을 따라야 한다.
- 승객은 모든 좌석 뒤에 있는 후면 문으로만 탑승할 수 있다. 차 안에서는 객실 앞쪽으로만 이동할 수 있고, 모든 좌석 앞에 있는 전면 문으로만 내릴 수 있다.
- 각 승객은 마지막으로 차지된 좌석 바로 뒤의 좌석에 앉아야 한다. 기차가 완전히 비어 있으면 승객은 맨 앞 좌석(1번 좌석)에 앉아야 한다.
- 하차할 때까지 승객은 자기 좌석을 떠날 수 없다.
- 각 역에서 목적지에 도착한 승객은 내린다. 도착한 승객보다 앞쪽에 앉은 승객은 자기 목적지에 도착하지 않았더라도 함께 내려야 한다.
- 한 번 내린 승객은 다시 탑승할 수 없다.
노선에는 1번부터 M번까지 번호가 붙은 M개의 역이 있다. 기차는 1번 역부터 M번 역까지 순서대로 정차한다. 승객은 1번부터 N번까지 번호가 붙어 있고, 각 승객의 운임, 승차 역, 목적지 역은 미리 정해져 있다.
회사는 목적지에 도착하는 승객만 받기를 원한다. 차장은 어떤 승객을 탑승시킬지, 그리고 어떤 순서로 탑승시킬지 정할 수 있다. 차장은 일부 승객의 탑승을 허용하지 않을 수도 있다.
목적지에 도착하는 승객만 태웠을 때 회사가 얻을 수 있는 최대 이익과, 그 이익을 내는 유효한 탑승 순서 하나를 구하라.
입력
첫 줄에 N과 M이 주어진다. 이어지는 N개의 줄에는 각각 x y c가 주어진다. x는 승차 역, y는 목적지 역, c는 운임이다. 모든 수는 양의 정수이며, 공백 한 칸으로 구분된다.
출력
첫 줄에 최대 이익 P를 출력한다.
둘째 줄에 최적해에서 목적지에 도착하는 승객 수 Num을 출력한다.
셋째 줄에 목적지에 도착한 승객의 번호를 탑승 순서대로 출력한다. 번호는 공백 한 칸으로 구분한다.
제한
- 모든 승객에 대해
- 최대 이익을 주는 승객 배치라면 어떤 배치든 정답으로 인정한다.
- 각 테스트는 최대 이익 P를 맞히면 배점의 60%, 출력해야 할 값을 모두 맞히면 100%를 받는다.