$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1036}$

$\texttt{Just the Beginning}$

$\texttt{Description}$

打完了末影龙，这并不是真正的结束。接下来，小 $\texttt{Z}$ 要挑战下一个 $\texttt{BOSS}$——凋灵。

凋灵不会自然生成，必须使用 $4$ 个灵魂沙和 $3$ 个凋零骷髅头颅来召唤。灵魂沙非常容易得到，而凋零骷髅头却不是。

凋零骷髅会生成再地狱堡垒里，我们假设小 $\texttt{Z}$ 仅在顶层刷凋零骷髅头，再每个时间点只能同时生成 $Q$ 个凋零骷髅，而只有小 $\texttt{Z}$ 打败了这 $Q$ 只凋零骷髅后才能进入下一个时间点。$Q$ 随着时间点的变化而变化。

小 $\texttt{Z}$ 所在的地狱堡垒顶层是一个 $n\times n$ 的正方形，但这其中只有一部分是地狱堡垒主体，其余全部是岩浆湖。若一只凋零骷髅的前后左右四个方向是岩浆湖或者地图边缘，则认为这一只骷髅是在地狱堡垒的边缘。

小 $\texttt{Z}$ 可以攻击任何的骷髅，但只有攻击不是在边缘的骷髅才能得到战利品。如果小 $\texttt{Z}$ 在与一个位于$(x_1,y_1)$位置的骷髅交战时，有另一只骷髅在其$R$的距离内，即 $(x_1-R,y_1-R)$ 至 $(x_1+R,y_1+R)$ 的范围内，则他不能攻击这只骷髅。

如果小 $\texttt{Z}$ 无法攻击所有的 $Q$ 个骷髅，则游戏结束，但小 $\texttt{Z}$ 有 $m$ 个道具，这个道具可以杀死任何一只凋零骷髅并且得到他的战利品，无论它是否在边缘或者在其他骷髅的范围内。

当表示 $P$ 组凋零骷髅位置的数据结束，则也算作游戏结束。

$\texttt{Input Format}$

第一行三个数，$n$，$m$，$R$。

后 $n$ 行，每行$n$个介于 $0$ 和 $1$ 的数字，若为 $0$ 表示这格是岩浆，反之为 $1$ 则为地狱堡垒主体。

第 $n+2$ 行，一个数 $P$，表示给出的凋零骷髅位置数据总数。

后 $P$ 行，每行至少 $1$ 个数，第一个数表示 $Q$，后 $2\times Q$ 个数表示凋零骷髅所在的位置 $x_1,y_1,x_2,y_2\cdots x_Q,y_Q$。

$\texttt{Output Format}$

一个数，表示小 $\texttt{Z}$ 能获得的战利品总数。

$\texttt{Sample}$

$\texttt{Input 1}$

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

$\texttt{Output 1}$

xxxxxxxxxx
2

$\texttt{Input 2}$

xxxxxxxxxx
7 1 1
0 0 1 1 1 0 0
0 0 1 1 1 0 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 1 1 1 0 0
0 0 1 1 1 0 0 
1
2 3 2 3 3

$\texttt{Output 2}$

xxxxxxxxxx
2

$\texttt{Hint}$

对于样例 $1$：第一刻杀死 $(3,3)$ 的骷髅，战利品 $+1$，第二刻由于两只骷髅都在边缘，所以只能用 $1$ 个道具杀死其中的一只骷髅得到 $1$ 个战利品，然后再杀死另一只骷髅不能得到战利品。

对于样例 $2$：两只骷髅在 $(3,2)$ 和 $(3,3)$，其中 $(3,2)$ 的骷髅位于边缘，此时两只骷髅均在对方的 $R$ 范围内，所以你不能攻击它们的任何一只，但你可以用道具消灭 $(3,2)$ 的骷髅，然后就可以消灭 $(3,3)$ 的骷髅了，可以得到 $2$ 个战利品。

注意，此处 $x,y$ 表示的是行和列，不是坐标系中的 $x$ 和 $y$。

对于 $20\%$ 的数据，所有格子都不是岩浆且骷髅不会出现在堡垒边缘；

对于 $40\%$ 的数据，$R=0$；

对于 $70\%$ 的数据，$Q=1$，$n≤20$；

对于 $100\%$ 的数据，$Q≤5$，$n≤50$，$R≤3$，每个时间点每两只凋零骷髅不会在同个位置。

对于全部数据点（$20$ 个）中的某 $5$ 个数据点，$M=0$。