007 - ほもの産

時間制限 1 秒 / メモリ制限 32 MB / 得点 100 / x 0 /


TLE
1sec
MLE
32MB
得点
100

問題

「第一章 ホモノ、おとこに飢える」
ホモノさんはホモです。ホモノさんは一生の夢でもあるHomo・Harlem(ホモ・ハーレム)の作成に向けて世界中からおとこのこを集めることにしました。
ホモノさんは座標(1,1)から座標(W,H)までの領域の周りに縄を張り無事N人のおとこのこを取り囲むことに成功しました。(Wは横 Hは縦です)
特別な力によってホモノさんはN人のおとこのこの初期位置をつかむことに成功しました。どうやらおとこのこたちは同じマスにいる場合もあるようです。また、日頃のストーキングの成果もあっておとこのこが手順1から手順Mまでの行動を繰り返してワープしていることに気がつきました。
おとこのこがワープを1回するごとに1秒が経過します。
ちなみにワープすることによって縄の外へ抜け出すことはできず、その場合はワープしないでその場に立ち止まって1秒待ちます。ここで、立ち止まった場合も手順は次へ進みます。
ところで、ホモノさんはホモであると同時に怠け者でもあるのでZ秒以内に自分がいるマスまたは自分がいるマスの周り8マスに来たおとこのこしか捕まえることができません。また、おとこのこを待っている間はホモノさんはその場を移動することができません。
あなたはこんなダメ人間かつ人間の屑なホモノさんが(X,Y)の場所にいたときに何人のおとこのこが捕まえれるかを調べることにしました。

入力

N M
W H X Y Z
x0 y1
x1 y1
.
.
.
xN-1 yN-1
命令 A0,1 命令 A0,2 ... 命令 A0,M
命令 A1,1 命令 A1,2 ... 命令 A1,M
.
.
.
命令 AN-1,1 命令 AN-1,2 ... 命令 AN-1,M

1行目に2つの整数N,Mが半角空白区切りで与えられる。
2行目に5つの整数W,H,X,Y,Zが半角空白区切りで与えられる。
3行目からN+2行まで
N人のおとこのこの最初にいる場所xi,yiが1行に与えられる
初期位置は他のおとこのこと同じ場合もある。
N+2+1行目からはi人目のおとこのこがワープする手順がまとめて1行に空白区切りで与えられる。
ここでの命令とは
1 - 上にAi,j移動する。-
2 - 下にAi,j移動する。-
3 - 左にAi,j移動する。-
4 - 右にAi,j移動する。-
という定義である。

出力

ホモノさんがZ秒までに捕まえられるおとこのこの人数を1行に出力せよ。
ただしホモノさんはこの作戦に全財産を注いでいるのでZ秒までにおとこのこを一人も捕まえられなかった場合は場合は死んでしまう。
もしおとこのこをZ秒以内にに一人も捕まえられなかった場合はホモノさんが死んだことを知らせる"Dead Homono"という一文を1行に出力せよ。
改行を忘れないようにすること。

制約

全ての入出力ケースについて以下を満たす。

  • 0 ≦ Ai,j ≦ 10
  • 1 ≦ W,H,xi,yi ≦ 50
  • 1 ≦ N,M ≦ 100
  • 1 ≦ Z ≦ 50

入出力例

入力例1

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

出力例1

2

解説

入力が見づらいと思っている人のために各おとこのこの初期位置とワープのパターンを示す。
一人目のおとこのこは左から1番目、上から1番目の位置に最初はいる。
一人目のおとこのこは右に1つ移動、下に1つ移動、左に1つ移動、上に1つ移動を繰り返す。
二人目のおとこのこは左から5番目、上から5番目の位置に最初はいる。
二人目のおとこのこは上に4つ移動、下に4つ移動、左に4つ移動、右に4つ移動を繰り返す。
三人目のおとこのこは左から5番目、上から1番目の位置に最初はいる。
三人目のおとこのこは左に1つ移動、左に1つ移動、上に1つ移動、下に1つ移動を繰り返す。

入力例2

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

解説

同時に複数のおとこのこを捕まえることができることに注意せよ

出力例2

9

入力例3

3 4
9 9 5 5 16 
1 1
9 9
3 3
1 10 1 10 1 10 1 10
3 8 1 8 4 8 2 8
1 0 4 0 2 0 3 0

出力例3

Dead Homono

解説

捕まえることができるおとこのこの数は0人なのでホモノさんは死んで世界に平和が訪れる。