P3800 Power 收集

题目背景

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

然而当时灵梦在 Power 达到 MAX 之前，不具有“上线收点”的能力，所以她想要知道她能收集多少 P 点，然而这个问题她答不上来，于是她找到了学 OI 的你。

题目描述

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

初始灵梦可以选择在第一行的任意一个格子出发。每秒她必须下移一格，同时可以向左或向右移动至多 $T$ 格，也可以不进行横向移动。横向移动不能在一次移动中折返。

移动视为瞬间完成，灵梦不会经过横向路径上的格子，只能获得每次移动后目标格子上的 P 点。

求灵梦从第一行移动到第 $N$ 行后，能够获得的 P 点价值总和的最大值。

输入格式

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

接下来 $K$ 行，每行包含三个整数 $x,y,v$，表示第 $x$ 行第 $y$ 列有一个价值为 $v$ 的 P 点。

保证同一个格子至多出现一个 P 点。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

9

数据范围与约定

对于 $40\%$ 的测试数据，满足 $1 \leq N,M,K,T \leq 200$。

对于 $100\%$ 的测试数据，满足：

• $1 \leq N,M,K,T \leq 4000$；
• $0 \leq v \leq 100$；
• 所有输入均为整数。

by-szc