스타트업 대표는 \(P\) 개의 프로젝트 중 일부를 골라 진행하려 한다. 프로젝트 \(i\) 를 완료하면 순이익 \(p_i\ (>0)\) 를 얻는다. 그러나 각 프로젝트는 특정 장비들을 필요로 한다. 장비 \(j\) 를 한 번이라도 구매하면 비용 \(c_j\ (>0)\) 가 들며, 한 번 구매한 장비는 여러 프로젝트가 공유할 수 있다.

어떤 프로젝트를 진행할지 자유롭게 고를 수 있다(아무것도 고르지 않아도 된다). 단, 진행하기로 한 프로젝트가 필요로 하는 모든 장비는 반드시 구매해야 한다. (얻는 순이익의 합) \(-\) (구매한 장비 비용의 합) 을 최대로 만들었을 때의 값을 구하여라. 아무것도 진행하지 않으면 값은 \(0\) 이다.

• \(0 \le P, M \le 200\)
• \(0 \le K \le 5000\)
• \(1 \le p_i \le 10^6\)
• \(1 \le c_j \le 10^6\)
• \(1 \le i \le P\), \(1 \le j \le M\), 같은 \((i,j)\) 쌍은 중복되지 않는다

첫 줄에 프로젝트 수 \(P\), 장비 수 \(M\), 요구 관계 수 \(K\) 가 주어진다.

둘째 줄에 \(p_1, \dots, p_P\) 가 주어진다(\(P=0\) 이면 빈 줄).

셋째 줄에 \(c_1, \dots, c_M\) 이 주어진다(\(M=0\) 이면 빈 줄).

이어지는 \(K\) 개의 줄에 각각 \(i\ j\) 가 주어지며, 프로젝트 \(i\) 가 장비 \(j\) 를 필요로 함을 뜻한다.

얻을 수 있는 최대 순이익을 정수 한 줄로 출력한다.

riseoj 작성

출처 Original