该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

位于迦南大陆的水晶城是一座由正方形街区组成的城市，每个街区都用整数坐标 $(x, y)$ 来表示，其中向东和向北的方向分别对应 $x$ 轴和 $y$ 轴的正方向。

每颗传送水晶上都标有可移动的相对位置 $(x, y)$（$x$、$y$ 为整数），在街区 $(X_1, Y_1)$ 使用该水晶的话，就可以传送到街区 $(X_1 + x, Y_1 + y)$。每颗传送水晶只能使用一次，使用后水晶就会消失。

从某个街区徒步行走的话，只能走到相邻的东、西、南、北方向中的某一个街区。在徒步行走时，必须支付固定的通行费。

住在街区 $(0, 0)$ 的犇犇现在打算前往街区 $(G_x, G_y)$（$G_x, G_y \geq 0$）。

发工资前的犇犇想要尽可能节省到达目的地之前使用水晶的费用和支付的通行费的总和。请你帮助犇犇计算出到达目的地的最小费用。

不过，今天的犇犇似乎很讨厌朝着远离目的地的方向移动，请在计算时假定不会向当前位置西边或南边的街区移动。

输入格式

第一行四个整数 $G_x，G_y，N，F$，分别表示犇犇打算前往的街区是 $(G_x, G_y)$，一共有 $N$ 个传送水晶，每走一个街区固定的通行费是 $F$；

接下来的 $N$ 行，每行三个整数 $x_i，y_i，c_i$表示一个传送水晶，可移动的相对位置是$(x_i，y_i)$，使用的费用是 $c_i$。

输出格式

一个整数，表示犇犇到达目的地最小费用。

样例

3 3 2 1
1 2 2
2 1 2

4

样例1说明

使用两次传送水晶到达目的地$(3，3)$，费用为 4。可以证明这是最小费用。

3 3 2 1
1 2 2
2 1 4

5

样例2说明

使用一次第一个移动水晶，然后往目标走三步，费用为 2+1+1+1=5。

5 3 5 2
5 0 6
5 0 6
2 2 6
0 2 3
3 1 6

11

5 3 5 1
5 0 6
5 0 6
2 2 6
0 2 3
3 1 6

8

数据范围

$0 \le G_x，G_y \le 100$

$0 \le N \le 50$

$1 \le F \le 200$

$0 \le x_i \le G_x，0 \le y_i \le G_y，(x_i，y_i) \neq (0， 0)$