P7936 [COCI 2007/2008 #5] BARICA

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$。 对于每一片荷叶，我们知道其附近的苍蝇数量。Barika 可以吃掉所有在她荷叶附近的苍蝇。 Barica 每吃一只苍蝇会获得 $1$ 个单位的能量，每进行一次跳跃消耗 $K$ 个单位的能量。如果 Barica 没有足够的能量，她就不能进行跳跃。 Barica 想通过 $1$ 号植物到达 $N$ 号植物，并获得尽可能多的能量。Barica 开始时没有能量，必须通过吃掉 $1$ 号植物附近的苍蝇来获取能量。 找到使得 Barica 达到目标的一种可行路径。

第一行，两个整数 $N$ 和 $K$。 接下来 $N$ 行，每行包含三个整数 $x_i$，$y_i$ 和 $z_i$，表示第 $i$ 号荷叶的坐标为 $(x_i,y_i)$，且其附近有 $z_i$ 只苍蝇。

第一行，输出到达终点后能量单位数量。 第二行，输出一个整数 $L$，表示 Barica 需要经过的植物个数。必须包含 $1$ 号和 $N$ 号植物。 接下来 $L$ 行，依次输出 Barica 需要经过的植物坐标。

对于 $100\%$ 的数据，$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$。 输入数据保证有解，但不保证有唯一解。 本题分值按照原比赛设置，满分 $70$ 分。