개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 보면 연꽃잎의 위치를 2차원 평면 위의 점으로 나타낼 수 있다. 왕눈이는 축에 평행한 직선으로만, 또 양의 방향으로만 뛸 수 있다. 따라서 왕눈이가 (x₁,y₁)에서 (x₂,y₂)로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야 한다.

• x₂ > x₁ 이고 y₂ = y₁
• y₂ > y₁ 이고 x₂ = x₁

왕눈이가 한 번 뛰는데는 K만큼의 힘이 든다. 만약 왕눈이의 힘이 K보다 작다면 더 이상 뛸 수 없다. 왕눈이는 처음에 1번 연꽃잎에 있고, N번 연꽃잎으로 이동하려고 한다. 맨 처음에 왕눈이가 가진 힘은 0이다.

각 연꽃잎에는 파리가 산다. 왕눈이는 연꽃잎에 사는 파리를 먹을 수 있다. 1마리의 파리를 먹을 때 마다 왕눈이는 1의 힘을 회복한다. 처음에 왕눈이의 힘이 0이므로 왕눈이가 뛰기 위해서는 1번 연꽃잎에 사는 파리를 먹어 힘을 얻어야 한다는 점에 주의하자.

당신은 왕눈이가 도착하고 난 뒤 가질 수 있는 힘의 최댓값을 구해야 한다. 더불어, 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램 또한 작성해야 한다.

입력 형식

첫 줄에 연꽃잎의 수 N과 한 번 이동하는데 필요한 힘 K가 주어진다. (2 ≤ N ≤ 300 000, 1 ≤ K ≤ 1000)

다음 N개의 줄에 걸쳐 각 연꽃잎의 좌표 X, Y와 파리의 양 F가 차례대로 주어진다. i+1번째 줄에 주어지는 좌표와 파리의 양은 i번 연꽃잎에 관한 정보이다. 연꽃잎의 좌표는 서로 다르다. (0 ≤ X, Y ≤ 100 000, 0 ≤ F ≤ 1000)

입력은 항상 답이 존재하도록 주어진다.

출력 형식

첫 줄에 N번 연꽃잎에 도착 한 뒤 최대 힘의 양을 출력한다.

두 번째 줄에는 1번 연꽃잎과 N번 연꽃잎을 포함하여 방문한 연꽃잎의 수 L을 출력한다.

다음 L개의 줄에 방문한 연꽃잎의 좌표들을 차례대로 출력한다.

만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.

예제 입력 1

6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5

예제 출력 1

5
4
1 1
2 1
2 3
3 3

예제 입력 2

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

예제 출력 2

36
5
1 1
1 2
2 2
3 2
3 3

예제 입력 3

9 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 1

예제 출력 3

2
3
5 5
7 5
7 7