Problem J
Speedy Slopes

Wally has spent a wonderful day hitting the slopes at Whirlwind Ridge, a new ski hill with an interesting twist, they’ve put directional “boost tracks" along some of the slopes, allowing skiers to quickly race to neighbouring slopes. Additionally they’ve recently become known for having the BEST hot chocolate around! Wally’s been waiting all year to get his hands on one. As Wally gets off the ski lift he spots a sign he must have missed before. Curious, he approaches the sign, but to his horror it reads “Reminder! The lodge will be closing early today!". Now he’s stuck at the top of the slopes in the northwest-most corner of the hill in a race to make it back to the lodge and the southeast-most corner! Luckily, while he’s been skiing, he’s also been recording the heights of all of the slopes (and valleys) on the hill. If he plans his route just right he might just make it in time for a hot chocolate! Wally isn’t the best at math so when he plans his route he makes the following assumptions to make it easier for himself:

1. Wally will start from a standstill

2. When going from a slope of height $h_i$ to one of height $h_f$ he will accelerate by $h_i - h_f$ meters per seconds

3. If there is a boost track between his current slope and a neighbouring one it will double his speed if he moves to the neighbouring slope

4. The acceleration from the change in height takes place immediately as he leaves a slope

5. The acceleration from a boost track will take place immediately thereafter

6. As he is travelling between slopes he moves at the same speed for the entire time

7. Slopes neighbouring in the cardinal directions (North, East, South, or West) are $100$ meters apart

8. Slopes neighbouring at a diagonal (Northeast, Northwest, Southeast, or Southwest) are $150$ meters apart

9. Wally will limit his speed to $2000$ m/s if he were to ever exceed it (he may not be good at math but he is an excellent skier)

Input

The first line of the input will contain two integers $n$ and $m$ ($2\leq n, m \leq 100$) the number of rows and columns respectively in Wally’s map. The following $n$ lines will contain $m$ integers $h_{i,j}$ ($0 \leq h_{i,j} \leq 255$) representing the heights of the slopes/valleys. The next line will contain a single integer $b$ ($0 \leq b \leq 8nm - 6n - 6m + 4$) the number of boost tracks on the slopes. The following $b$ lines will contain four integers $r_1, c_1, r_2, c_2$ ($0\leq r_1, r_2 < n$ and $0\leq c_1, c_2 < m$) representing that there is a boost track going from slope $(r_1,c_1)$ to $(r_2,c_2)$. No boost track will appear twice.

Output

Output a single number $t$ the shortest amount of time (in seconds) that it will take Wally to get to the lodge with absolute error less than $10^{-4}$. Note: it will always be possible for Wally to make it back to the lodge

3 3
10 5 8
5 5 8
8 8 1
0

46.666666667

3 3
10 5 8
5 5 8
8 8 1
3
0 0 0 1
0 2 1 2
1 2 2 2

30.714285714