Bomb Removal

Problem

縦H×横Wのグリッド上にN個の点火された導火線とそれぞれに対する1つの爆弾が配置されている。それぞれの導火線と爆弾は、L_i個のマスからなるpath_i上に配置され、path_iのj番目のマスを(px_ij, py_ij)とする。各爆弾はpath_iの最後のマス(px_iLi, py_iLi)に存在する。導火線の火は初期状態(0秒時点)でマス(px_i1, py_i1)にあり、1秒間に1マス進む((px_i1, py_i1),(px_i2, py_i2),...,(px_iLi, py_iLi)の順に進む)。

最初、ロボットがマス(sx, sy) にいる。このロボットは今いるマスの隣接する8方向のマスに1進む、または、そのマスに留まるのに1秒かかる。ただし、グリッドの外や爆弾のあるマスには移動することができない。ロボットは導火線の火があるマス上にいるとき消火することができる(同じマスに2つ以上の導火線の火がある場合はそれら全てを消すことができる)。

爆弾は導火線の火がマス(px_iLi, py_iLi)に到達したときに爆発する(path_iの途中で導火線の火がマス(px_iLi, py_iLi)を通過したときは爆弾は爆発しない)。 全ての爆弾を爆発させずに全ての導火線の火を消火させるための最短の時間を出力せよ。ただし、どのように移動しても爆弾を爆発させてしまう場合は-1を出力せよ。なお、初期状態(0秒時点)でロボットが導火線の火の上にいる場合、消火することができる。

Input

入力は以下の形式で与えられる。

W H N
sx sy
L1 path1
L2 path2
...
LN pathN

1行目に3つの整数W, H, Nが空白区切りで与えられる。2行目に2つの整数sx, syが空白区切りで与えられる。3行目からN+2行目に L_i と path_i が与えられる。path_i は以下の形式で与えられる。

pxi1 pyi1 pxi2 pyi2 ... pxiLi pyiLi

Constraints

• 2 ≤ H,W ≤ 20
• 1 ≤ N ≤ 5
• 1 ≤ sx ≤ W
• 1 ≤ sy ≤ H
• 2 ≤ L_i ≤ H+W
• 1 ≤ px_ij ≤ W
• 1 ≤ py_ij ≤ H
• path_iの隣り合うマスは上下左右に隣接している。
• 導火線は互いに独立している(他の導火線に影響しない)。
• 爆弾はマス(sx, sy)には置かれない。

Output

ロボットが全ての導火線の火を消火させるための最短時間または -1 を出力せよ。

Sample Input 1

2 2 1
2 1
3 1 1 1 2 2 2

Sample Output 1

1

サンプル1に対応する図は以下の通りである。

ロボットは1秒後に左下の(1, 2)のマスに移動することにより消火することができる。

Sample Input 2

2 2 1
2 1
2 1 1 1 2

Sample Output 2

-1

サンプル2に対応する図は以下の通りである。

ロボットは、(1, 1)または(2, 2)のマスに移動する、または今いるマス(2, 1)に留まることができるがいずれにせよ1秒後に爆弾が爆発してしまう。

Sample Input 3

3 3 2
1 3
3 2 3 2 2 2 1
5 2 1 1 1 1 2 2 2 3 2

Sample Output 3

2

サンプル3に対応する図は以下の通りである。

ロボットは、(2, 2)のマスに移動し、(1, 2)のマスに移動することにより2秒で全ての導火線の火を消火することができる。

Sample Input 4

3 3 1
2 2
2 2 2 2 1

Sample Output 4

0

ロボットは、初期状態(0秒時点)で(2, 2)のマスにいて、導火線の火も(2, 2)のマスにあるので0秒で消火することができる。

---