Problem Description

Barica is an extraordinary frog. She lives in a pond with $N$ floating lily pads. These lily pads are numbered from $1$ to $N$ and their positions can be represented by pairs of coordinates. Barica can jump between these lily pads, but she is afraid of jumping diagonally or in the negative direction.

Specifically, she can jump from coordinates $(x_1, y_1)$ to another coordinates $(x_2, y_2)$ only if:

• $x_2 > x_1$ and $y_2 = y_1$, or
• $y_2 > y_1$ and $x_2 = x_1$.

For each lily pad, we know the number of flies nearby. Barica can eat all the flies on her lily pad.

Barica gains $1$ unit of energy for each fly she eats and consumes $K$ units of energy for each jump. If Barica does not have enough energy, she cannot make a jump.

Barica wants to travel from the $1$st lily pad to the $N$th lily pad and gain as much energy as possible. Barica starts with no energy and must gain energy by eating the flies on the $1$st lily pad.

Find a feasible path for Barica to reach her goal.

Input Format

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain three integers $x_i$, $y_i$, and $z_i$, representing that the $i$-th lily pad has coordinates $(x_i, y_i)$ and $z_i$ flies nearby.

Output Format

The first line should output the number of energy units after reaching the destination.

The second line should output an integer $L$, representing the number of lily pads Barica needs to pass through, including the $1$st and $N$th lily pads.

The next $L$ lines should output the coordinates of the lily pads Barica needs to pass through in order.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5
4
1 1
2 1
2 3
3 3 

Sample Input #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

Sample Output #2

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

Sample Input #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 

Sample Output #3

2
3
5 5
7 5
7 7 

Notes

For $100\%$ of the data, $2 \le N \le 3 \times 10^5$, $1 \le K \le 1000$, $0 \le x_i, y_i \le 10^5$, $0 \le z_i \le 1000$.

The input data guarantees a solution, but it is not guaranteed to be unique.

This problem is scored according to the original competition settings, with a maximum of $70$ points.

见题面 Input 部分

见题面 Output 部分