Power收集

题目背景

据说在红雾异变时,博丽灵梦单身前往红魔馆,用十分强硬的手段将事件解决了。 然而当时灵梦在 Power 达到 MAX 之前,不具有“上线收点”的能力,所以她想要知道她能收集多少 P 点,然而这个问题她答不上来,于是她找到了学 OI 的你。

题目描述

可以把游戏界面理解成一个 $N$ 行 $M$ 列的棋盘,有 $K$ 个格子上有 $P$ 点,其价值为 $\operatorname{val}(i,j)$。 初始灵梦可以选择在第一行的任意一个格子出发,每秒她必须下移一格。 灵梦具有一个左右移动的速度 $T$,可以使她每秒向左或右移动至多 $T$ 格,也可以不移动,并且不能折返。移动可视为瞬间完成,不经过路途上的点,只能获得目标格子的 P 点。 求最终她能获得的 POWER 值最大是多少?

输入输出格式

输入格式


第一行四个数字,$N,M,K,T$。 接下来 $K$ 行每行 $3$ 个数字 $x,y,v$,代表第 $x$ 行第 $y$ 列有一个 $val$ 为 $v$ 的 P 点,数据保证一个格子上最多只有 $1$ 个 P 点。

输出格式


一个数字

输入输出样例

输入样例 #1

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

输出样例 #1

9

说明

对于 $40\%$ 的测试点,$1 \le N,M,T,K \le 200$。 对于 $100\%$ 的测试点,$1 \le N,M,T,K \le 4000$。 $v \le 100$,$N,M,K,T$ 均为整数。 by-szc