Description

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.

Input Format

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 Format

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

3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3

9

Hint

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