DuLL

윈도우에서 DLL(동적 링크 라이브러리)은 프로그램이 실행 중에 불러올 수 있는, 미리 컴파일된 함수들의 모음을 담은 파일이다. DLL의 두 가지 주요 장점은 다음과 같다. (1) 동시에 여러 프로그램이 같은 DLL을 사용하더라도 메모리에는 그 DLL의 사본이 하나만 있으면 된다. (2) DLL은 프로그램과 분리되어 있으므로, 그 DLL을 사용하는 프로그램을 다시 컴파일하지 않고도 독립적으로 업그레이드할 수 있다.

우리 시스템의 DLL은 특별할 것이 없다. 이 밋밋한(dull) DLL, 즉 DuLL 은 각각 고정된 크기의 메모리를 차지하며, 메모리에 올라가 있는 동안 그 크기는 변하지 않는다. 마찬가지로 각 프로그램도 자신만의 고정된 메모리 요구량을 가지며, 실행되는 동안 그 크기는 변하지 않는다. 또한 각 프로그램은 실행되는 내내 특정 DuLL들이 메모리에 올라가 있기를 요구한다. 따라서 필요한 메모리 양이 바뀌는 순간은 오직 새 프로그램이 실행될 때와, 실행 중이던 프로그램이 종료될 때뿐이다. 새 프로그램이 실행을 시작하면, 그 프로그램이 요구하는 DuLL 중 아직 메모리에 없는 것들이 모두 메모리에 올라간다. 실행 중이던 프로그램이 종료되면, 현재 실행 중인 어떤 프로그램에게도 더는 필요하지 않은 DuLL들이 메모리에서 내려간다.

특정 DuLL은 어느 순간에도 메모리에 최대 한 개의 사본만 존재한다. 다만 같은 프로그램의 여러 인스턴스가 동시에 실행될 수 있다. 이 경우 프로그램의 각 인스턴스는 자신만의 메모리를 따로 차지하지만, DuLL은 서로 무관한 두 프로그램이 공유하는 것과 똑같은 방식으로 인스턴스들 사이에서도 공유된다.

여러 프로그램을 그들이 필요로 하는 DuLL과 함께 실행할 때, 전 과정에서 사용된 최대 메모리 사용량 을 구하여라. 어느 시점의 메모리 사용량은 (현재 실행 중인 모든 프로그램 인스턴스의 크기 합)에 (현재 메모리에 올라가 있는 모든 DuLL의 크기 합)을 더한 값이다.

입력은 하나 이상의 데이터 집합으로 이루어지며, 마지막에는 0 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 세 정수 $N$, $P$, $S$ 가 주어진다. $N$은 사용할 수 있는 DuLL의 개수로 $1 \le N \le 20$, $P$는 실행될 수 있는 프로그램의 개수로 $1 \le P \le 9$, $S$는 기록된 상태 전이의 개수로 $1 \le S \le 32$ 이다.

다음 줄에는 각 DuLL의 크기(바이트)를 나타내는 정수 $N$개가 공백으로 구분되어 주어진다($1 \le \text{크기} \le 1000$). 각 DuLL에는 순서대로 문자 라벨 'A', 'B', 'C', …, 최대 'T'까지가 암묵적으로 붙는다. 즉 첫 번째 정수는 'A'의 크기, 두 번째 정수는 'B'의 크기이며, 이런 식으로 이어진다.

다음 $P$개의 줄에는 각 프로그램의 정보가 한 줄에 하나씩 주어진다. 각 줄은 프로그램의 크기(바이트, $1 \le \text{크기} \le 1000$)를 나타내는 정수 하나로 시작하고, 이어서 그 프로그램이 요구하는 DuLL을 나타내는 $1$개 이상 $N$개 이하의 문자가 온다. 프로그램 크기와 DuLL 라벨 사이에는 공백이 하나 있지만, 라벨들 사이에는 공백이 없다. 라벨의 순서는 의미가 없으며, 모두 유효한 DuLL 라벨이고, 같은 라벨이 두 번 나오지 않는다. 각 프로그램에는 순서대로 정수 라벨 1, 2, 3, …, 최대 9까지가 암묵적으로 붙는다.

각 데이터 집합의 마지막 줄에는 $S$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 양수 $q$($1 \le q \le P$)이면 프로그램 $q$의 새로운 실행이 시작되었음을, 음수 $-q$($1 \le q \le P$)이면 프로그램 $q$의 실행 하나가 종료되었음을 뜻한다. 전이는 실제로 일어난 순서대로 주어진다. 모든 값은 유효한 프로그램 번호이며, 값이 음수 $-q$인 경우 그 시점에 프로그램 $q$의 인스턴스가 최소 하나는 실행 중이다.

각 데이터 집합마다 한 줄을 출력한다. 그 줄에는 해당 데이터 집합을 실행하는 전 과정에서 필요했던 최대 메모리 양 만을 출력한다.