Wall Breaker KND

Problem

KND君は会津大学に在籍する学生プログラマである。彼はプログラマーであるとともに格闘家でもある。そんな彼は甘党であることで知られてるが、特に生クリームが大好物である。生クリームを食べればコンクリートの壁を数回壊すことができるようになるほどである。そのパワーに興味をもった彼の隣人は、生クリームたっぷりの新商品、「マトクリーム」を用いて実験をすることにした。

その実験は、まず迷路を用意しKND君をそこに閉じ込める。その迷路には鍵がかかった扉、扉を開けるための鍵、マトクリームがそれぞれ1つずつ別のマスに存在する。彼は落ちている鍵を拾い、扉の鍵を開けることで外に脱出することが可能である。鍵を持っていなくても扉があるマスに移動することは可能である。また、マトクリームを食べることで迷路の壁を N 回だけ壊すことができるようになる。ただし外壁を壊して迷路の外に出ることはできない。さて、彼は最小何回のマス移動で迷路を脱出できるだろうか。

サンプル2つの迷路と最短の脱出経路は次の図で示される。SはKND君の初期位置、Mはマトクリーム、Kは鍵、Dは扉を表す。

Input

入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式で与えられる。 入力の終了を2つのゼロを含む行で示す。

(迷路の入力)
xs ys
xm ym
xk yk
xd yd
N

ここで、

• 迷路の入力:
  まず迷路の幅と高さを表す2つの整数 W , H が来る。次に 2 * H - 1 行の入力がある。このうちの奇数行目は横に隣合うマスの間の壁の有無を表す。最初に空白が1つあり、 W - 1 個の1か0が来る。1は壁があること、0は壁がないことを表す。偶数行目は縦に隣合うマスの間の壁の有無を表す。こちらは W 個の1か0が来る。同様に1は壁があること、0は壁がないことを表す。
• x_s y_s:主人公の初期位置のマスの座標
• x_m y_m:マトクリームのマスの座標
• x_k y_k:鍵のマスの座標
• x_d y_d:扉のマスの座標
• N:マトクリームをとった場合に迷路の壁を壊せる回数

Constraints

入力は以下の条件を満たす。

• 入力はすべて整数。
• 2 ≤ W, H ≤ 20
• 0 ≤ x_s, x_m, x_k, x_d < W
• 0 ≤ y_s, y_m, y_k, y_d < H
• 0 ≤ N ≤ 100
• 主人公の初期位置のマスの座標、マトクリームのマスの座標、鍵のマスの座標、扉のマスの座標は互いに別の座標である。
• 扉に入ることが不可能なデータセットはない。

Output

各テストケースにつきKND君が迷路から脱出する最小のマス移動回数を一行に出力せよ。

Sample Input

3 3
 0 0
0 0 0
 0 0
0 0 1
 0 1
0 0
0 1
1 1
2 2
1
5 5
 0 1 0 0
1 0 0 1 0
 1 0 1 0
0 1 0 0 1
 0 1 1 0
0 1 0 1 0
 1 1 1 0
0 0 0 0 0
 0 0 1 1
0 0
1 0
4 4
0 1
2
0 0

Sample Output

4
15