교착 상태 감지

시스템에는 프로세스 여러 개와 자원 종류 여러 개가 있다. 자원 종류는 메모리 페이지, DMA 채널, 입출력 포트 같은 것이고, 종류마다 인스턴스 개수가 정해져 있다. 프로세스는 실행하려면 인스턴스를 확보해야 하고, 종류별로 필요한 개수는 프로세스마다 다르다. 필요한 인스턴스를 모두 확보한 프로세스는 실행을 마치고 종료하면서 확보한 인스턴스를 그때 한꺼번에 반납한다. 종료 전에 인스턴스를 반납하는 프로세스는 없다.

프로세스는 다른 프로세스가 무엇을 하는지 신경 쓰지 않고 필요한 인스턴스를 하나씩 확보한다. 필요한 종류에 남은 인스턴스가 없으면 다른 프로세스가 종료하면서 반납할 때까지 기다린다. 교착 상태는 프로세스 둘 이상이 서로가 끝나기를 영원히 기다리는 상황이다. 이런 식으로 생긴다. 프로세스 A가 자원 X의 하나뿐인 인스턴스를 확보하고, 프로세스 B가 다른 자원 Y의 하나뿐인 인스턴스를 확보한다. 그다음 A는 Y의 인스턴스를, B는 X의 인스턴스를 확보하려 한다. Y의 인스턴스는 B가 쥔 것 하나뿐이므로 A는 B가 끝나기 전에는 Y를 얻지 못하고, B도 A가 끝나기 전에는 X를 얻지 못한다. 프로세스 셋 이상이 얽힌 교착 상태도 있다.

시스템이 시작한 시각부터 어느 시각까지의 자원 할당 기록이 주어진다. 시스템이 교착 상태를 피할 수 없는 상태에 빠진 시각을 구하라. 할당 순서를 잘 고르면 교착 상태를 대개 피할 수 있지만, 교착 상태를 피할 수 없는 상태에서는 지금까지의 할당만으로 이미 교착 상태가 정해지며 이후 할당 순서를 어떻게 잡아도 달라지지 않는다.

자원 종류가 R1과 R2 두 가지이고 프로세스가 P1과 P2 둘인 시스템을 보자. R1의 인스턴스는 3개, R2의 인스턴스는 4개다. P1은 실행을 마치는 데 R1 3개와 R2 2개가 필요하고, P2는 R1 1개와 R2 3개가 필요하다. 이 시스템의 할당 기록은 아래와 같다.

시각 4에 P2가 R1을 확보하면서 남은 R1 인스턴스가 P1에 아직 필요한 개수보다 적어졌고, P1은 P2가 종료해 인스턴스를 반납하기를 기다려야 한다. 시각 5에는 P1이 P2에 아직 필요한 R2 인스턴스를 확보해 P2도 P1을 기다려야 한다. 이 시각에 교착 상태를 피할 수 없게 되었다. 시각 4까지는 P2를 먼저 끝내서 교착 상태를 피할 수 있다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

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$는 프로세스 개수이고 $2 \le p \le 300$인 정수다. 프로세스 번호는 1부터 $p$까지다. $r$은 자원 종류 개수이고 $1 \le r \le 300$인 정수다. 자원 종류 번호는 1부터 $r$까지다. $t$는 기록의 길이이고 $1 \le t \le 200000$인 정수다.

$l_j$는 자원 종류 $j$의 인스턴스 중 처음에 쓸 수 있는 개수이고 $1 \le l_j \le 100$인 정수다. $n_{i,j}$는 프로세스 $i$에 필요한 자원 종류 $j$의 인스턴스 개수이고 $0 \le n_{i,j} \le l_j$인 정수다. 모든 $i$에 대해 $n_{i,1}, \dots, n_{i,r}$ 중 적어도 하나는 0이 아니다. $P_k$와 $R_k$ 쌍은 시각 $k$의 할당 기록이고, 프로세스 $P_k$가 자원 종류 $R_k$의 인스턴스 하나를 확보했다는 뜻이다.

기록에는 모순이 없다. 필요하지 않은 인스턴스를 확보하는 프로세스는 없고, 종료한 뒤에 인스턴스를 확보하는 프로세스도 없으며, 쓸 수 있는 인스턴스가 하나도 없는 종류를 확보하는 일도 없다.

시스템이 교착 상태를 피할 수 없는 상태에 빠진 시각을 출력한다. 시각 $t$의 기록까지 처리한 뒤에도 교착 상태를 피할 수 있으면 -1을 출력한다.