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 事先没有足够的能量，她就无法进行跳跃。

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$，表示 Barica 应该经过的植物数量（包括植物 $1$ 和植物 $N$）。

接下来的 $L$ 行，输出 Barica 应该经过的植物序列（每行输出对应植物的坐标）。

样例

输入样例 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