Problem Statement

Crystal City is a town famous for the use of warp crystals, which let you move to another place instantly.
However, you cannot move to an arbitrary position: for each crystal, the relative position you can move to from your current location is fixed.

• Crystal City is a town made up of square blocks laid out in a grid.
  Each block is represented by integer coordinates $(x,y)$, where east and north correspond to the positive directions of the $x$-axis and the $y$-axis, respectively.
• Each warp crystal has a relative position $(x,y)$ ($x,y$ are integers) written on it,
  and using it at block $(X_1,Y_1)$ lets you warp to block $(X_1+x,Y_1+y)$.
• From a block, you can move on foot only to an adjacent block to the east, west, south, or north.
  Each such move requires paying a fixed toll.

Added at 22:48: A crystal disappears once it is used.

Input

$G_x \ G_y \ N \ F$
$x_1 \ y_1 \  c_1$
$\vdots$
$x_N \ y_N \ c_N$

The input is given separated by spaces.
The first line contains the coordinates $(G_x, G_y)$ of the destination block, the number $N$ of crystals Chris has, and the toll $F$ for moving on foot to an adjacent block.
From the 2nd line to the $N+1$-th line, the relative position $(x_i,y_i)$ that each crystal can move to and its price $c_i$ are given.

All inputs are integers and satisfy the following constraints.
$ 0 \le Gx,Gy \le 100$
$ 0 \le N \le 50 $
$ 1 \le F \le 200 $
$0 \le x_i \le Gx$, $0 \le y_i \le Gy$, $ (x_i, y_i) \neq (0,0) $
$1 \le c_i \le 200 $
As the constraints also show, today Chris does not use crystals that move west or south.
As stated in the problem statement, he also does not move on foot to a block to the west or south.

Output

Output the minimum cost for Chris to get from $(0,0)$ to $(Gx,Gy)$. Print a newline at the end.

Sample

Sample 1

Input

3 3 2 1
1 2 2
2 1 2

Output

4

For example, moving using only crystals as shown below minimizes the cost.

Sample 2

Input

3 3 2 1
1 2 2
2 1 4

Output

5

Walking costs less than using the second crystal.

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