F. Painting a Picture
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob and Alice live in a country that can be represented as a $$$2D$$$ grid of $$$n$$$ rows and $$$m$$$ columns where rows are numbered from top to bottom and columns are numbered from left to right. Bob lives at coordinates $$$(1,1)$$$ and Alice lives at coordinates $$$(n,m)$$$.

On Valentines Day, Bob wants to visit his girlfriend Alice and he would like to paint a picture to give to her. The picture needs $$$C$$$ different colors. Bob currently doesn't have any color so he would like to purchase colors and paint the picture on the way to his girlfriend to gain some time.

There are some shops in the country where each shop sells only one color and has an unlimited amount of units of that color.

The price of the paints of colors doesn't matter for Bob so he can spend any amount of money, but the time is crucial. So he would like to know what is the minimum time to go from his home to Alice's home with the picture ready.

Since Bob is smart, he can mix $$$2$$$ colors to get another color, but this operation will take time and depends on the color. So there are $$$K$$$ possible mixtures defined as follows: $$$(c_{1},c_{2},c_{3},t)$$$, which means mixing $$$c_{1}$$$ with $$$c_{2}$$$ will produce $$$c_{3}$$$ and takes $$$t$$$ time.

Bob can move from $$$(a,b)$$$ to $$$(c,d)$$$ if and only if $$$1\leq c\leq n$$$ and $$$1\leq d\leq m$$$ and $$$|a-c|+|b-d|=1$$$ and it takes $$$1$$$ unit of time.

Note that : drawing time and buying time are negligible

Input

The first line contains $$$4$$$ integers $$$n$$$, $$$m$$$ $$$(1\leq n,m \leq 100)$$$, $$$C$$$ $$$(1\leq C \leq 7)$$$ and $$$K$$$ $$$(0\leq K \leq \frac{C*(C-1)}{2})$$$.

The next $$$n$$$ lines each contain a string of length $$$m$$$ containing only digits. If $$$s_{i,j} = 0$$$ then the cell is empty otherwise it represents the color that the shop sells at coordinates $$$(i,j)$$$.

The next $$$K$$$ lines each contains $$$4$$$ integers $$$c_{1}, c_{2}, c_{3}, t$$$ the description of the mixture $$$(1\leq c_{1}, c_{2}, c_{3} \leq C,c_{1}\ne c_{2},c_{1}\ne c_{3},c_{2}\ne c_{3})$$$, $$$(1\leq t \leq 10^{5})$$$. It is guaranteed that each unordered pair $$$(c_{1},c_{2})$$$ can appear at most one time.

Output

If it is possible to prepare the picture, print the minimum time required for Bob reach Alice's home with his picture ready. Otherwise print -1.

Examples
Input
5 5 3 1
00012
00000
00000
00000
30000
1 2 3 2
Output
10
Input
5 5 3 1
00012
00000
00000
00000
30000
1 2 3 10
Output
16