P7302 [NOI1998] Free Pies

SERKOI has recently released a game called "Free Pies". The game is played on a stage. The stage has a width of $w$ cells (numbered from $1$ to $w$ from left to right), and the player occupies one cell. At the beginning, the player may stand anywhere on the stage and holds a tray. The figure below shows a moment when the ceiling height is $4$ cells and the player is catching pies.  After the game starts, pies continuously appear from the top cells of the stage ceiling and fall straight down. The player moves left and right to catch the pies. Each second, the player may move $1$ or $2$ cells to the left, move $1$ or $2$ cells to the right, or stay in place. If at some moment a pie arrives exactly at the cell where the player is standing, the player collects that pie. If a pie lands in a cell where the player is not present, the pie disappears. Write a program to help the player collect pies so that the sum of the scores of the collected pies is maximized.

The first line contains two positive integers separated by spaces, giving the stage width $w$ and the number of pies $n$. The next $n$ lines each provide information about one pie. Each line contains three positive integers, which are: the time $t_i$ when the pie reaches the stage, the index $p_i$ of the cell where it falls, and the score value $v_i$. The game starts at time $0$. In the input file, adjacent items on the same line are separated by one space. In the input data, it is possible that two pies have the same $t_i$ and $p_i$.

Output one number, representing the maximum total score the player can obtain.

For $100\%$ of the data, $1 \leq w \leq 10^8$, $1 \leq n \leq 10^5$, $1 \leq t_i \leq 10^8$, $1 \leq p_i \leq w$, $1 \leq v_i \leq 1000$。 Translated by ChatGPT 5