编程题：动态规划
巴里卡是一只不同寻常的青蛙。她住在一个池塘里，有$$N$$株植物漂浮在水面上。植物编号为1到$$N$$。从上面看时，每个植物的位置由一对坐标给出。让巴里卡与众不同的是她害怕斜向和反向跳跃。更准确地说，她可以从坐标$$（x1，y1）$$处的一个植物跳到坐标$$（x2，y2）$$处的另一个植物，前提是：
•$$x2>x1，y2=y1$$
或
•$$y2>y1，x2=x1$$
对于每一种植物，我们知道其附近的苍蝇数量。巴里卡可以用她敏捷的舌头吃掉她所在植物附近的所有苍蝇。
巴里卡每吃一只苍蝇就吸收一个能量单位，每跳一次就消耗$$K$$个能量单位。如果事先没有足够的能量单位，巴里卡就跳不起来。
巴里卡希望从1号植物到$$N$$号植物，并在到达后尽可能获得最大的能量。巴里卡一开始没有能量，她必须从植物1周围的苍蝇那里收集能量进行第一次跳跃。
找到巴里卡为了实现目标应该旅行的植物序列。
### 输入格式:
第一行输入包含两个整数$$N$$和$$K（2≤N≤300 000, 1≤K≤1000）$$被一个空格隔开。
以下$$N$$行中的每一行都包含三个整数$$X、Y$$和$$F（0≤ X、Y≤ 100 000, 0≤F≤1000）$$用空格隔开，这意味着在坐标$$（X，Y）$$处有一个植物，周围有$$F
$$。
输入中的第一个植物是植物1，第二个是植物2等。
没有两个植物会共享同一对坐标。
注：输入数据将保证跳转序列始终存在，尽管不一定是唯一的。
### 输出格式:
在第一行输出最终的能级。
输出一个整数$$L$$，即巴里卡应该旅行的植物数量，包括植物1和$$N$$。
在下面的$$L$$行上，输出$$Barica$$应该移动的植物序列。
### 输入样例1:
in
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5
### 输出样例1:
out
5
4
1 1
2 1
2 3
3 3
### 输入样例2:
in
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:
out
36
5
1 1
1 2
2 2
3 2
3 3
### 输入样例3:
in
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:
out
2
3
5 5
7 5
7 7
答案：若无答案欢迎评论
•$$x2>x1，y2=y1$$
或
•$$y2>y1，x2=x1$$
对于每一种植物，我们知道其附近的苍蝇数量。巴里卡可以用她敏捷的舌头吃掉她所在植物附近的所有苍蝇。
巴里卡每吃一只苍蝇就吸收一个能量单位，每跳一次就消耗$$K$$个能量单位。如果事先没有足够的能量单位，巴里卡就跳不起来。
巴里卡希望从1号植物到$$N$$号植物，并在到达后尽可能获得最大的能量。巴里卡一开始没有能量，她必须从植物1周围的苍蝇那里收集能量进行第一次跳跃。
找到巴里卡为了实现目标应该旅行的植物序列。
### 输入格式:
第一行输入包含两个整数$$N$$和$$K（2≤N≤300 000, 1≤K≤1000）$$被一个空格隔开。
以下$$N$$行中的每一行都包含三个整数$$X、Y$$和$$F（0≤ X、Y≤ 100 000, 0≤F≤1000）$$用空格隔开，这意味着在坐标$$（X，Y）$$处有一个植物，周围有$$F
$$。
输入中的第一个植物是植物1，第二个是植物2等。
没有两个植物会共享同一对坐标。
注：输入数据将保证跳转序列始终存在，尽管不一定是唯一的。
### 输出格式:
在第一行输出最终的能级。
输出一个整数$$L$$，即巴里卡应该旅行的植物数量，包括植物1和$$N$$。
在下面的$$L$$行上，输出$$Barica$$应该移动的植物序列。
### 输入样例1:
in
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5
### 输出样例1:
out
5
4
1 1
2 1
2 3
3 3
### 输入样例2:
in
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:
out
36
5
1 1
1 2
2 2
3 2
3 3
### 输入样例3:
in
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:
out
2
3
5 5
7 5
7 7
答案：若无答案欢迎评论
