K. Power收集

Type: RemoteJudge

2000ms

250MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。

然而当时灵梦在 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 点。

一个数字

对于 $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