P7936 [COCI 2007/2008 #5] BARICA

Barica is an unusual frog. She lives in a pond with $N$ lily pads floating on the water surface. The lily pads are numbered from $1$ to $N$, and their positions can be described by a pair of coordinates. Barica can jump between these lily pads, but she is afraid of jumping diagonally and of jumping in the negative direction. More precisely, she can jump from coordinate $(x_1,y_1)$ to another coordinate $(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 near the lily pad she is on. For each fly Barica eats, she gains $1$ unit of energy. Each jump costs $K$ units of energy. If Barica does not have enough energy, she cannot jump. Barica wants to travel from lily pad $1$ to lily pad $N$ and end up with as much energy as possible. Barica starts with no energy and must gain energy by eating the flies near lily pad $1$. Find a feasible path that allows Barica to reach the goal.

The first line contains two integers $N$ and $K$. The next $N$ lines each contain three integers $x_i$, $y_i$, and $z_i$, meaning that lily pad $i$ is at $(x_i,y_i)$ and there are $z_i$ flies nearby.

The first line outputs the amount of energy units after reaching the destination. The second line outputs an integer $L$, the number of lily pads Barica needs to pass through. It must include lily pads $1$ and $N$. The next $L$ lines output, in order, the coordinates of the lily pads Barica should pass through.

Constraints: 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 guarantees that a solution exists, but it is not necessarily unique. The score for this problem follows the original contest setting, with a full score of $70$ points. Translated by ChatGPT 5