問題文

ぴなさんは、 $N$ 行 $M$ 列のマスからなる街に住んでいます。 $i$ 行 $j$ 列のマスを $(i,j)$ と表現します。
ぴなさんはマス $(1,1)$ に住んでおり、学校はマス $(N,M)$ にあります。
また、この街の $K$ 個のマス $(A_i,B_i)\ (1 \leq i \leq K)$ は「不思議なマス」と呼ばれるマスです。

ぴなさんは、各整数時刻に次の行動のいずれかができます。なお、ぴなさんには「疲労度」という値が定まっており、初めこれは $0$ です。

• $1$ 秒かけて、上下左右に隣り合うマスに移動する。この時、疲労度は変わらない。
• いまいるマスが不思議なマス $(A_i,B_i)$ の時、その場に留まったまま $C_i$ 秒時間を巻き戻す。ただし、時間を巻き戻したあと $1$ 秒間は動くことができない。
  これにより、ぴなさんの疲労度が $D_i$ 増える。
  なお、この操作は同じマスで繰り返し行うこともできるが、その場合も時間を巻き戻したあと $1$ 秒間は行動できない。

ぴなさんは遅刻せずに登校したいですが、あまり疲れたくありません。初め、ぴなさんの疲労度は $0$ です。
今は時刻 $0$ です。 $T$ 秒後までに登校する時、ぴなさんの疲労度として有り得る最小の値を求めてください。なお、マス $(N,M)$ には時刻 $T$ 秒丁度までに到着すれば良いです。
$T$ 秒後までに登校することが不可能な場合、 -1 と出力してください。

入力

$N\ M\ K\ T$
$A_1\ B_1\ C_1\ D_1$
$\vdots$
$A_K\ B_K\ C_K\ D_K$

• $1 \leq N \leq 80$
• $1 \leq M \leq 80$
• $0 \leq K \leq NM-2$
• $1 \leq T \leq 10^9$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq M$
• $(A_i,B_i) \neq (1,1),(N,M)$
• $(A_i,B_i) \neq (A_j,B_j)\ (i \neq j)$
• $1 \leq C_i \leq 10^9$
• $1 \leq D_i \leq 10^9$
• 入力は全て整数

出力

最後に改行してください。

サンプル

2 4 1 3
1 2 28 19

19

2 1 0 25

0