击杀

题目描述

武士藤藤准备击杀地图上的幽灵。

地图为 $n\times m$（行，列）的整点网格图，坐标从左向右从下到上从 $0$ 编号。开始藤藤可以从地图的任意的左侧进入，最后藤藤将从地图的右侧离开。

藤藤在地图上的行进有一些奇妙的性质：

1. 藤藤每单位时间会向右移动一单位长度，以尽快从地图上离开。

2. 当一只幽灵与藤藤坐标重合，藤藤就会将其击杀。

在纵向，每单位时间藤藤可以快速移动 $[-delta,+delta]$ 单位长度。藤藤的移动速度极快，可以认为移动时不与任何幽灵坐标重合。

每只幽灵都有一定的能力值，第 $i$ 行第 $j$ 列幽灵的能力值记为 $A_{i,j}$。藤藤希望其击杀的幽灵能力值之和最大。

输入格式

第一行包括四个整数 $n,m,delta,num$。

接下来 $num$ 行，每行包括三个非负整数 $x,y,A_{x,y}$，表示幽灵坐标和能力值，并保证不会有幽灵在地图范围之外。

输出格式

输出包括一个整数，为被击杀幽灵能力值的和的最大值。

样例

样例输入

4 4 1 4
1 1 6
1 2 7
2 2 3
1 3 5

样例输出

18

数据范围