Problem Statement

Pina lives in a town consisting of a grid with $N$ rows and $M$ columns. The cell in row $i$ and column $j$ is denoted by $(i,j)$.
Pina lives at cell $(1,1)$, and the school is at cell $(N,M)$.
In addition, $K$ cells $(A_i,B_i)\ (1 \leq i \leq K)$ of this town are called "mysterious cells".

At each integer time, Pina can take one of the following actions. Pina has a value called "fatigue", which is initially $0$.

• Spend $1$ second to move to a cell adjacent vertically or horizontally. The fatigue does not change.
• If the current cell is a mysterious cell $(A_i,B_i)$, stay in place and rewind time by $C_i$ seconds. However, Pina cannot move for $1$ second after rewinding time.
  This increases Pina's fatigue by $D_i$.
  This operation may be repeated on the same cell, but in that case too, Pina cannot act for $1$ second after rewinding time.

Pina wants to get to school without being late, but does not want to get too tired. Initially, Pina's fatigue is $0$.
The current time is $0$. When getting to school within $T$ seconds, find the minimum possible value of Pina's fatigue. It suffices to arrive at cell $(N,M)$ by exactly time $T$ seconds at the latest.
If it is impossible to get to school within $T$ seconds, print -1.

Input

$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$
• All input values are integers.

Output

Print a newline at the end.

Sample

2 4 1 3
1 2 28 19

19

2 1 0 25

0