P3800 Power Collection

It is said that during the Scarlet Mist incident, Reimu Hakurei went alone to the Scarlet Devil Mansion and resolved the incident with very forceful means. However, before her Power reached MAX, Reimu did not have the ability to "collect at the top line" (上线收点), so she wanted to know how many P points she could collect. She could not answer this question, so she turned to you, who study OI.

Treat the game screen as an $N$-row by $M$-column grid. There are P points on $K$ cells, and their values are $\operatorname{val}(i,j)$. Initially, Reimu may choose any cell in the first row to start. Each second, she must move down by exactly one row. Reimu has a horizontal speed $T$, allowing her each second to move left or right by at most $T$ columns, or not move horizontally at all, and she cannot reverse direction within a single move. Movement is considered instantaneous: she does not pass through intermediate cells en route and can only obtain the P point on the destination cell. Compute the maximum possible total value of all P points she can obtain.

The first line contains four integers, $N,M,K,T$. Each of the next $K$ lines contains three integers $x,y,v$, indicating that there is a P point with $\operatorname{val}=v$ at row $x$, column $y$. It is guaranteed that there is at most $1$ P point on any cell.

Output a single integer, the maximum total value of P points Reimu can obtain.

For $40\%$ of the testdata, $1 \le N,M,T,K \le 200$. For $100\%$ of the testdata, $1 \le N,M,T,K \le 4000$, $0 \le v \le 100$, and $N,M,K,T$ are all integers. by-szc Translated by ChatGPT 5