金币收集

题目描述

游戏界面为一个$N$行$M$列的棋盘，有$K$个格子上有金币，其价值为$val(i,j)$。

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

灵梦具有一个左右移动的速度$T$，可以使她每秒向左或右移动至多$T$格，也可以不移动，并且不能折返。移动可视为瞬间完成，不经过旅途上的点，只能获得目标格子的金币。求最终她能获得的金币价值最大是多少？

输入格式

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

接下来$K$行每行$3$个数字$x$，$y$，$v$代表第$x$行第$y$列有$val$为$v$的金币，数据保证一个格子上最多只有$1$个金币点。

输出格式

一行一个整数，表示答案。

数据范围与提示

• 对于$40\%$的数据，$1 \leq N$，$M$，$T$，$K \leq 200$；
• 对于$100\%$的数据，$1 \leq N$，$M$，$T$，$K \leq 4000$，$0 < v < 100$。

样例

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

9

见coin2.in

见coin2.out