縦H×横Wのグリッド上にN個の点火された導火線とそれぞれに対する1つの爆弾が配置されている。それぞれの導火線と爆弾は、Li個のマスからなるpathi上に配置され、pathiのj番目のマスを(pxij, pyij)とする。各爆弾はpathiの最後のマス(pxiLi, pyiLi)に存在する。導火線の火は初期状態(0秒時点)でマス(pxi1, pyi1)にあり、1秒間に1マス進む((pxi1, pyi1),(pxi2, pyi2),...,(pxiLi, pyiLi)の順に進む)。
最初、ロボットがマス(sx, sy) にいる。このロボットは今いるマスの隣接する8方向のマスに1進む、または、そのマスに留まるのに1秒かかる。ただし、グリッドの外や爆弾のあるマスには移動することができない。ロボットは導火線の火があるマス上にいるとき消火することができる(同じマスに2つ以上の導火線の火がある場合はそれら全てを消すことができる)。
爆弾は導火線の火がマス(pxiLi, pyiLi)に到達したときに爆発する(pathiの途中で導火線の火がマス(pxiLi, pyiLi)を通過したときは爆弾は爆発しない)。 全ての爆弾を爆発させずに全ての導火線の火を消火させるための最短の時間を出力せよ。ただし、どのように移動しても爆弾を爆発させてしまう場合は-1を出力せよ。なお、初期状態(0秒時点)でロボットが導火線の火の上にいる場合、消火することができる。
入力は以下の形式で与えられる。
W H N sx sy L1 path1 L2 path2 ... LN pathN
1行目に3つの整数W, H, Nが空白区切りで与えられる。2行目に2つの整数sx, syが空白区切りで与えられる。3行目からN+2行目に Li と pathi が与えられる。pathi は以下の形式で与えられる。
pxi1 pyi1 pxi2 pyi2 ... pxiLi pyiLi
ロボットが全ての導火線の火を消火させるための最短時間または -1 を出力せよ。
2 2 1 2 1 3 1 1 1 2 2 2
1
サンプル1に対応する図は以下の通りである。
ロボットは1秒後に左下の(1, 2)のマスに移動することにより消火することができる。
2 2 1 2 1 2 1 1 1 2
-1
サンプル2に対応する図は以下の通りである。
ロボットは、(1, 1)または(2, 2)のマスに移動する、または今いるマス(2, 1)に留まることができるがいずれにせよ1秒後に爆弾が爆発してしまう。
3 3 2 1 3 3 2 3 2 2 2 1 5 2 1 1 1 1 2 2 2 3 2
2
サンプル3に対応する図は以下の通りである。
ロボットは、(2, 2)のマスに移動し、(1, 2)のマスに移動することにより2秒で全ての導火線の火を消火することができる。
3 3 1 2 2 2 2 2 2 1
0
ロボットは、初期状態(0秒時点)で(2, 2)のマスにいて、導火線の火も(2, 2)のマスにあるので0秒で消火することができる。