Maximizing Power on a Chessboard Grid

You are given a grid with N rows and M columns, which can be viewed as a chessboard. There are K cells on the board that contain some points. For a cell at row i and column j that contains points, its value is denoted by \(\operatorname{val}(i,j)\). All other cells have a value of 0.

Initially, Reimu (the character) can start from any cell in the first row. Every second, she moves down exactly one row. Additionally, she has a horizontal speed of T which allows her to move left or right up to T cells per second (or she may choose not to move horizontally). Note that the horizontal movement is instantaneous and she only collects the points of the destination cell (points in cells passed over during horizontal movement are not collected). Also, note that she cannot reverse her vertical progress.

Your task is to help Reimu choose a path from the top row to the bottom row such that the total collected points (or POWER) is maximized. In other words, for each move from row \(r\) to \(r+1\), if she is in column \(j\) then she can move to any cell in row \(r+1\) with column index \(j'\) satisfying \(|j' - j| \le T\). Determine the maximum POWER value she can gain by the time she reaches row \(N\).

Note: If a cell is referenced multiple times in the input, sum up its points.

inputFormat

The first line contains four integers: N, M, K, and T, where N is the number of rows, M is the number of columns, K is the number of cells that contain points, and T is the maximum horizontal shift allowed per move.

Then follow K lines, each containing three integers: r, c, and p, indicating that the cell in row r and column c contains p points (\(\operatorname{val}(r,c)=p\)). Rows and columns are 1-indexed. Cells not listed have 0 points.

outputFormat

Output a single integer, the maximum POWER value that Reimu can collect on her way from the first row to the N-th row.

sample

3 4 4 1
1 2 5
2 2 6
2 3 2
3 4 7

14