P13566 "CZOI-R5" The Frog's Trip.

Little L is a frog, and he is now preparing to travel in City A.

City A is an $n\times m$ matrix. There is a given number $k$. There is also a variable $w$, initially $0$. Let $(r,c)$ denote the cell in row $r$ and column $c$. In this matrix, there are $t$ special points. The $i$-th one is at $(x_i,y_i)$ with type $p_i$ ($p_i\in\{1,2\}$). If $p_i=2$, it has an additional attribute $s_i$. **It is guaranteed that there do not exist $i,j$ such that $i\neq j$ and $x_i=x_j,y_i=y_j$.** Little L starts at $(1,1)$. He can perform any number of one of the following jump operations **until he reaches** $(n,m)$. Suppose he is currently at $(a,b)$: - Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a+i,b)$ is a type $2$ special point. Then jump to $(a+h+1,b)$. - Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a,b+i)$ is a type $2$ special point. Then jump to $(a,b+h+1)$. - Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a+i,b+i)$ is a type $2$ special point. Then jump to $(a+h+1,b+h+1)$. After each jump, suppose it lands at $(X,Y)$. If $(X,Y)$ is the $Z$-th special point, then: - If $p_Z=1$, then $w\leftarrow w+1$. - If $p_Z=2$, let $w\leftarrow w-s_Z$. If in some plan, at any moment $w

The first line contains $4$ integers $n,m,k,t$. The next $t$ lines each start with an integer $p_i$, then: - If $p_i=1$, input $2$ integers $x_i,y_i$, representing a type $1$ special point. - If $p_i=2$, input $3$ integers $x_i,y_i,s_i$, representing a type $2$ special point.

Output one integer on the first line, the answer.

**[Sample Explanation #1]** Note: Each point below represents a cell. A red arrow is one jump, and the tail of the arrow is $(X,Y)$. Yellow points are special points with $p_i=1$. Green points are special points with $p_i=2$. The following $15$ plans are valid:  The following $5$ plans are invalid, because in these plans, after Little L reaches $(2,3)$, $w=-1