Background

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.

Problem 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