你正在分析一个包含多个进程和多种资源（如内存页、DMA 通道和 I/O 端口）的系统。每种资源都有一定数量的实例。进程必须获取资源实例才能执行。进程所需的某种资源实例数量取决于该进程本身。进程在获取所有所需资源后，最终会完成执行并终止。随后，这些资源实例会被释放，以便其他进程使用。在终止之前，没有任何进程会释放实例。进程会不断尝试逐个获取所需的资源实例，而不考虑其他进程的行为。由于进程是独立运行的，它们有时可能会因为死锁而无法完成执行。

当不再有所需的资源实例可用时，进程必须等待，直到其他进程在终止时释放资源。死锁是指两个或多个进程相互等待对方终止，且遗憾的是，这种情况会永远持续下去。这种情况发生于以下场景：进程 A 获取了资源 X 的唯一实例，而进程 B 获取了资源 Y 的唯一实例；此后，A 尝试获取 Y 的一个实例，而 B 尝试获取 X 的一个实例。由于除了 B 获取的 Y 实例外没有其他 Y 实例，A 在 B 完成执行前永远无法获取 Y，而 B 在 A 完成执行前也永远无法获取 X。可能存在涉及三个或更多进程的更复杂的死锁情况。

你的任务是接收系统的资源分配时间日志（从系统启动到某个时间点），以确定系统何时进入了“死锁不可避免”的状态。死锁通常可以通过适当的分配顺序来避免，但“死锁不可避免”的状态是指：已经进行了一些资源分配，且从那时起无论采取何种后续分配顺序，都无法避免死锁。

让我们考虑下面样例输入 1 对应的例子。系统有两种资源 $R_1$ 和 $R_2$，以及两个进程 $P_1$ 和 $P_2$。系统有 3 个 $R_1$ 实例和 4 个 $R_2$ 实例。进程 $P_1$ 需要 3 个 $R_1$ 和 2 个 $R_2$ 才能完成执行，而进程 $P_2$ 需要 1 个 $R_1$ 和 3 个 $R_2$。资源分配时间日志如下所示。

在时间 4，$P_2$ 获取了 $R_1$，可用 $R_1$ 的数量变得小于 $P_1$ 对 $R_1$ 的需求。因此，$P_1$ 必须等待 $P_2$ 终止并释放该实例。然而，在时间 5，$P_1$ 获取了 $P_2$ 完成执行所需的 $R_2$，因此 $P_2$ 也必须等待 $P_1$；此时死锁变得不可避免。

注意，在时间 4 时，通过先完成 $P_2$ 仍然可以避免死锁（样例输入 2）。

输入格式

输入包含单个测试用例，格式如下：

$p \ r \ t$ $l_1 \dots l_r$ $n_{1,1} \dots n_{1,r}$ $\vdots$ $n_{p,1} \dots n_{p,r}$ $P_1 \ R_1$ $\vdots$ $P_t \ R_t$

$p$ 是进程数量，为 2 到 300 之间的整数。进程编号为 1 到 $p$。$r$ 是资源种类数量，为 1 到 300 之间的整数。资源种类编号为 1 到 $r$。$t$ 是时间日志的长度，为 1 到 200,000 之间的整数。$l_j$ ($1 \le j \le r$) 是资源种类 $j$ 最初可用的实例数量，为 1 到 100 之间的整数。$n_{i,j}$ ($1 \le i \le p, 1 \le j \le r$) 是进程 $i$ 完成执行所需的资源种类 $j$ 的实例数量，为 0 到 $l_j$ 之间的整数。对于每个 $i$，至少有一个 $n_{i,j}$ 不为零。每一对 $P_k$ 和 $R_k$ ($1 \le k \le t$) 表示时间 $k$ 的资源分配日志，意味着进程 $P_k$ 获取了一个资源 $R_k$ 的实例。

你可以假设时间日志是一致的：没有进程会获取不必要的资源实例；没有进程会在终止后获取实例；且进程不会在某种资源实例不可用时获取该资源。

输出格式

输出系统进入“死锁不可避免”状态的时间。如果系统在时间 $t$ 时仍然可以避免死锁，则输出 -1。

样例

样例输入 1

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1

样例输出 1

5

样例输入 2

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

样例输出 2

-1