P7196 [CTSC2002] Rat Extermination Operation.

Recently, some highly fertile rats have become rampant in the sewer. The rat extermination task force is planning to eliminate them. The sewer has only east-west and north-south pipes, as shown in the figure.  Members of the task force have powerful weapons. At certain times $t$, they will place weapons at certain positions $(x,y)$. The weapons they use include: 1. Powerful Bomb: Its attack range is limited to inside the pipes. It covers the area in the vertical and horizontal directions whose distance from $(x,y)$ does not exceed $L$, but it cannot pass through sewer walls. It explodes immediately after being placed, and all rats within the attack range will be killed. 2. Mysterious Ray: Its attack range is the circle centered at $(x,y)$ with radius $R$, and it can pass through sewer walls. After the ray is cast at time $t$, all rats within the attack range immediately fall into a coma, lose consciousness, and stop all physiological activities, and they can only recover at time $t+3$ (keeping the direction they had before losing consciousness). If a rat in a coma is attacked by the ray again, its recovery will be postponed by another $3$ time units. For example, if a rat is attacked by the ray at time $t$ and time $t+1$, then it will remain unconscious until time $t+3+3$. After regaining consciousness, the rat will continue its previous physiological activities. 3. Timed Bomb: Its attack range includes only $(x,y)$. After being placed at time $t$, it will explode at time $t+3$. When it explodes, all rats at point $(x,y)$ will be killed. 4. Biological Bomb: Its attack range includes only $(x,y)$. It explodes immediately after being placed, changing the sex of all rats at point $(x,y)$ (regardless of age: female becomes male, male becomes female), but it does not affect the rats’ normal physiological activities. Although the task force is strong, the rats are not to be underestimated. We define that the interval between two adjacent times is one time unit. Starting from time $t=0$, each rat moves from its initial position in some initial direction. As long as there is a pipe ahead, such as reaching point $\texttt{A}$ along direction $\texttt{N}$ in the figure, the rat will keep moving forward at speed $1$. Otherwise, if there is a pipe only on the left or only on the right, such as reaching point $\texttt{B}$ along direction $\texttt{E}$ in the figure, and it can no longer continue forward, it will spend one time unit turning $90$ degrees in place toward that direction; that is, it will change its direction to face $\texttt{S}$. If there are pipes on both the left and the right, such as reaching point $\texttt{C}$ along direction $\texttt{W}$ in the figure, the rat will remember how many times it has been in this situation. If it is the odd-numbered time, it turns left; if it is the even-numbered time, it turns right. If it is at the end of a dead end, such as reaching point $\texttt{D}$ along direction $\texttt{W}$ in the figure, it will spend two time units turning right twice consecutively; that is, it will change its direction to face E. If at time $t$ a certain point has exactly two rats, one adult male and one adult female, then they will stay at that point for two time units to reproduce. At time $t+2$, they will give birth at that point to one baby rat facing each direction that has a pipe. Baby rats in the north-south directions are male, and those in the east-west directions are female. For example, at point $\texttt{C}$ in the figure, if at time $t$ there are exactly two rats and both are adults of different sexes, then at time $t+2$ three baby rats will be born at that point, facing $\texttt{N}$, $\texttt{S}$, and $\texttt{E}$, with sexes male, male, and female respectively. A baby rat starts moving immediately upon birth, while adult rats need to rest for one more time unit, i.e., they resume activity at time $t+3$ (both rats keep their directions from before reproduction). A baby rat needs to grow for $5$ time units to become an adult rat. The task force has now made a rat extermination plan, including the positions, times, and types of weapons to be placed in the sewer pipes. You need to help them compute the effect of the operation. If, during the execution of the plan, the number of rats exceeds a certain limit, a plague will break out. #

The first line contains $4$ integers $L, R, m, n(0\le L,R\le 10,1\le m,n\le 50)$, where $L$ is the effective attack distance of the powerful bomb, $R$ is the radius of the mysterious ray, and $m$ and $n$ are the size of the sewer map. The range of the $x$ coordinate is $[1,m]$, and the range of the $y$ coordinate is $[1,n]$. Lines $2$ to $m+1$ give the sewer structure map. We use direction number $1$ for $\texttt{N}$ (north), $2$ for $\texttt{E}$ (east), $4$ for $\texttt{S}$ (south), and $8$ for $\texttt{W}$ (west). The $j$-th number $c_{i,j}$ in line $i+1$ represents the sum of all direction numbers of pipes connected at point $(i,j)$. For example, in the figure, the sum of direction numbers at point $\texttt{B}$ is $12$. Line $m+2$ contains an integer $K（1\le K\le 50）$, the number of rats at time $0$ (all rats are adults at this time). Lines $m+3$ to $m+K+2$ each describe one rat, including its initial coordinates $(x,y), (1\le x\le m, 1\le y\le n)$, its facing direction (’$\texttt{E}$’,’$\texttt{S}$’,’$\texttt{W}$’,’$\texttt{N}$’), and its sex (’$\texttt{X}$’ = male, ’$\texttt{Y}$’ = female). The input guarantees that every rat is inside the pipes. Line $m+K+3$ contains two integers $P，Limit(1\le P, Limit\le 100)$, which represent the number of weapons the task force plans to use and the maximum number of rats allowed to prevent a plague. Lines $m+K+4$ to $m+K+P+3$ each describe one weapon, including the weapon type ($1$ = powerful bomb, $2$ = mysterious ray, $3$ = timed bomb, $4$ = biological bomb), the placement time $t(t\ge 1)$, and the placement coordinates $(x,y) (1\le x\le m, 1\le y\le n)$. The input guarantees that weapons are placed inside the pipes. Weapons are given in non-decreasing order of placement time. The last line contains an integer $Time(1\le Time\le 1000)$, which indicates the end time of the simulation. $Time$ is guaranteed to be greater than all weapon placement times. #

Output a single integer. If a plague breaks out, output $-1$; otherwise, output the number of rats at time $Time$. #

### Sample Explanation  Translated by ChatGPT 5