問題文

Crystal City は、瞬時に別の場所に移動できるワープクリスタルが使えることで有名な街です。
ただ任意の位置に移動できるわけではなく、クリスタルごとに現在地から移動できる相対位置が決まっています。

• Crystal City は正方形の区画を敷き詰めてできている街です。
  各区画は整数座標 $(x,y)$ で表現され、東と北が それぞれ$x$ 軸、$y$ 軸の正の向きに対応します。
• 各ワープクリスタルには移動できる相対位置 $(x,y)$（$x,y$ は整数）が記されており、
  区画 $(X_1,Y_1)$ で使うと区画 $(X_1+x,Y_1+y)$ にワープ出来ます。
• ある区画から徒歩で移動できるのは隣接する東西南北のいずれかの区画です。
  その際一律の通行料を払う必要があります。

22:48 追記　クリスタルは一度使ったら無くなります。

入力

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

入力は空白区切りで与えられます。
１行目には目的地の区画の座標 $(G_x, G_y)$、クリス君が所持するクリスタルの数 $N$、隣接する区画へ徒歩で移動するときの通行料 $F$ が与えられます。
２行目から$N+1$行目には各クリスタルの移動できる相対位置 $(x_i,y_i)$と値段 $c_i$ が与えられます。

入力は全て整数であり、以下の制約を満たします。
$ 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 $
制約からもわかりますが、今日のクリス君は西や南へ移動するクリスタルを使いません。
問題文で述べたように西や南の区画に徒歩で移動することもありません。

出力

クリス君が $(0,0)$ から $(Gx,Gy)$ へたどり着く最小コストを出力して下さい。 最後に改行してください。

サンプル

サンプル1

入力

3 3 2 1
1 2 2
2 1 2

出力

4

例えば以下のように、クリスタルのみを使って移動するとコストが最小です。

サンプル2

入力

3 3 2 1
1 2 2
2 1 4

出力

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