Deadlock Detection

A system runs several processes and provides several kinds of resource, such as memory pages, DMA channels and input output ports. Each kind of resource has a fixed number of instances. A process has to acquire instances to run, and the number of instances it needs of each kind depends on the process. Once a process has acquired every instance it needs, it finishes and terminates, releasing all of them at that moment. No process releases an instance before it terminates.

Processes acquire instances one at a time and pay no attention to what the other processes do. A process that needs an instance of a kind with nothing available waits until some other process terminates and releases one. A deadlock is a situation in which two or more processes wait for each other to terminate, and do so forever. Here is how it happens. Process A acquires the sole instance of resource X and process B acquires the sole instance of another resource Y. After that A tries to acquire an instance of Y and B tries to acquire an instance of X. There is no instance of Y other than the one held by B, so A will never acquire Y before B finishes, while B will never acquire X before A finishes. Deadlocks involving three or more processes exist too.

You are given the resource allocation log of the system, from its start to a certain time. Report the time at which the system fell into a deadlock-unavoidable state. Deadlock can usually be avoided by choosing a good allocation order, but in a deadlock-unavoidable state the allocations made so far already force a deadlock, whatever order the later allocations take.

Consider a system with two kinds of resource R1 and R2 and two processes P1 and P2. There are three instances of R1 and four instances of R2. P1 needs three instances of R1 and two instances of R2 to finish, and P2 needs one instance of R1 and three instances of R2. Its allocation log is traced below.

At time 4, P2 acquired R1 and the number of free instances of R1 dropped below what P1 still needs, so P1 has to wait for P2 to terminate and release its instances. At time 5, P1 acquired an instance of R2 that P2 still needs, so P2 has to wait for P1 as well. The deadlock became unavoidable at that time. At time 4 the deadlock is still avoidable by finishing P2 first.

The input is a single test case in the following format.

p r t
l_1 l_2 ... l_r
n_1,1 n_1,2 ... n_1,r
...
n_p,1 n_p,2 ... n_p,r
P_1 R_1
...
P_t R_t

$p$ is the number of processes, an integer with $2 \le p \le 300$. The processes are numbered 1 through $p$. $r$ is the number of resource kinds, an integer with $1 \le r \le 300$. The resource kinds are numbered 1 through $r$. $t$ is the length of the time log, an integer with $1 \le t \le 200000$.

$l_j$ is the number of instances of resource kind $j$ that are available at the start, an integer with $1 \le l_j \le 100$. $n_{i,j}$ is the number of instances of resource kind $j$ that process $i$ needs, an integer with $0 \le n_{i,j} \le l_j$. For every $i$, at least one of $n_{i,1}, \dots, n_{i,r}$ is nonzero. The pair $P_k$ and $R_k$ is the allocation log entry at time $k$: process $P_k$ acquired one instance of resource kind $R_k$.

The time log is consistent. No process acquires an instance it does not need, no process acquires an instance after it terminates, and no process acquires an instance of a resource kind that has none available.

Print the time at which the system fell into a deadlock-unavoidable state. If the system can still avoid deadlock after the log entry at time $t$, print -1.