给定N个植物（植物的编号分别为1到N）的坐标，以及每个植物上的飞虫数。一只青蛙要从第一个植物跳到第N个植物上去。跳跃的规则如下：
它现在的位置在(x1, y1) 目标位置在(x2,y2)则两点的坐标要满足：
•x2 > x1 and y2 = y1, or
•y2 > y1 and x2 = x1
在每个植物上青蛙会吃掉所有的飞虫，且每一只飞虫都会让它产生一个单位的能量。但它从一个植物到另一个要用掉K个能量（如果能量不到K它将无法跳跃）。青蛙的初始能量为0，要解决的问题是：青蛙到第N个植物后能得到的最高能量。
输入：
第一行两个整数 N和 K (2 ≤ N ≤ 300 000, 1 ≤ K ≤ 1000)
接下来N行，每行三个整数 X, Y和F (0 ≤ X, Y ≤ 100 000, 0 ≤ F ≤ 1000)
输入的第i+1行表示第i个植物的坐标为(X, Y) 有F个飞虫在上面， 输入保证没有两个植物在同一点坐标上。且一定能从1跳到N，但可能有多种最优方案。
输出：
第一行一个数表示青蛙的能量。
接下来一个整数 L,表示青蛙得到这个能量值走过的路线长度。
接下来L行，每行一个坐标表示青蛙跳过的植物。
样例：
输入：
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5
输出：
5
4
1 1
2 1
2 3
3 3
输入：
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
输出：
36
5
1 1
1 2
2 2
3 2
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
输出：
2
3
5 5
7 5
7 7