Description

可以把游戏界面理解成一个 $N$ 行 $M$ 列的棋盘，有 $K$ 个格子上有 P 点，其价值为 $\operatorname{val}(i,j)$。

初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。

灵梦具有一个左右移动的速度 $T$，可以使她每秒向左或右移动至多 $T$ 格，也可以不移动，并且在单次移动中不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的 P 点。

求最终她能获得的所有 P 点的价值总和最大是多少？

Input Format

第一行四个整数，$N,M,K,T$。

接下来 $K$ 行每行 $3$ 个整数 $x,y,v$，代表第 $x$ 行第 $y$ 列有一个 $\operatorname{val}$ 为 $v$ 的 P 点，数据保证一个格子上最多只有 $1$ 个 P 点。

Output Format

一个整数，表示灵梦能获得的 P 点的价值总和的最大值。

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

9

Hint

对于 $40\%$ 的测试点，$1 \le N,M,T,K \le 200$。

对于 $100\%$ 的测试点，$1 \le N,M,T,K \le 4000$，$0 \le v \le 100$，$N,M,K,T$ 均为整数。

by-szc