레이팅 미적용Barica는 특이한 개구리이다. 그녀는 수면에 \(N\)개의 수초가 떠 있는 연못에 산다. 수초에는 \(1\)부터 \(N\)까지 번호가 붙어 있다. 위에서 내려다볼 때 각 수초의 위치는 좌표 쌍으로 주어진다. Barica가 특이한 점은 대각선 방향과 음의 방향으로 뛰는 것을 무서워한다는 것이다. 더 정확히 말하면, 그녀는 좌표 \((x_1, y_1)\)의 수초에서 좌표 \((x_2, y_2)\)의 수초로 다음 경우에만 뛸 수 있다:
- \(x_2 > x_1\)이고 \(y_2 = y_1\), 또는
- \(y_2 > y_1\)이고 \(x_2 = x_1\)
각 수초에 대해 그 주변에 있는 파리의 수를 알고 있다. Barica는 재빠른 혀로 자기가 있는 수초 근처의 파리를 전부 잡아먹을 수 있다.
Barica는 파리 한 마리를 먹을 때마다 에너지 1단위를 얻고, 뛸 때마다 에너지 \(K\)단위를 쓴다. 뛰기 전에 에너지가 충분하지 않으면 뛸 수 없다.
Barica는 수초 \(1\)에서 수초 \(N\)으로 가되, 도착했을 때 남은 에너지가 최대가 되기를 원한다. Barica는 처음에 에너지가 없으며, 첫 점프를 위한 에너지는 수초 \(1\) 주변의 파리에게서 모아야 한다.
Barica가 목표를 이루기 위해 지나야 하는 수초들의 순서를 구하시오.
입력의 첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(K\) (\(2 \le N \le 300\,000\), \(1 \le K \le 1000\))가 주어진다.
다음 \(N\)개의 줄에는 공백으로 구분된 세 정수 \(X\), \(Y\), \(F\) (\(0 \le X, Y \le 100\,000\), \(0 \le F \le 1000\))가 주어진다. 좌표 \((X, Y)\)에 수초가 있고 그 주변에 파리가 \(F\)마리 있다는 뜻이다. 입력의 첫 번째 수초가 수초 \(1\), 두 번째가 수초 \(2\)인 식이다.
좌표 쌍이 같은 두 수초는 없다.
참고: 입력 데이터는 점프 순서가 항상 존재함을 보장한다. 단, 유일하지 않을 수도 있다.
첫째 줄에 최종 에너지를 출력한다.
정수 \(L\), 즉 수초 \(1\)과 \(N\)을 포함하여 Barica가 지나야 하는 수초의 개수를 출력한다.
다음 \(L\)개의 줄에 Barica가 지나야 하는 수초들의 좌표를 순서대로 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 55
4
1 1
2 1
2 3
3 38 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 1536
5
1 1
1 2
2 2
3 2
3 39 5
5 5 10
6 5 2
7 5 1
5 6 2
6 6 6
7 6 2
5 7 1
6 7 2
7 7 12
3
5 5
7 5
7 7