모두에게 필요한 것은 데이트뿐

Anne은 사람들 사이의 맞선을 주선하는 것을 좋아하며, 'Anne Dating Center'라는 스타트업 회사를 열었다. 어느 날, 그녀는 PC 학교 학생들과의 맞선 축제를 열고 싶어 하는 IC 학교로부터 의뢰를 받는다. Anne은 먼저 맞선 축제에 참여하고 싶어 하는 모든 PC 학교 학생의 정보를 수집한다. 그런 다음 수집한 정보를 IC 학생들에게 나누어 주고, IC 학생들에게 PC 학교에서 원하는 데이트 상대를 제출하라고 요청한다. 한 IC 학생은 PC 학교에서 여러 명의 원하는 상대를 가질 수 있다. IC와 PC 학생 모두에게서 예상치 못한 요구가 하나 있는데, 그것은 최소 및 최대 데이트 횟수이다. 맞선 축제를 위해, 각 학생은 데이트 횟수에 대한 최소 기대치를 가진다. 반면, 다가오는 시험 때문에 학생은 최대 데이트 횟수에 제한을 가진다. 요약하면, IC 학교와 PC 학교의 모든 학생은 각자 참여할 데이트 횟수의 최소값과 최대값을 가진다. 또한, 한 학생은 축제 동안 여러 번 데이트를 할 수 있지만, IC 학생과 PC 학생의 쌍은 두 학생 사이에 기껏해야 한 번만 데이트를 할 수 있다.

m명의 IC 학생과 n명의 PC 학생 사이의 맞선을 위해 다음과 같은 세 가지 제약이 주어진다. (1) IC 학교 학생들의 k개의 원하는 상대 목록, (2) IC 학생들이 원하는 데이트 횟수의 최소값과 최대값, (3) PC 학생들이 원하는 데이트 횟수의 최소값과 최대값. Anne은 IC 학생 u의 원하는 상대 목록에 PC 학생 v가 있을 때에만 u와 v 사이에 데이트를 주선할 수 있다. 따라서 원하는 상대의 수가 최소 데이트 횟수보다 적은 IC 학생 u가 있다면, Anne은 u를 위한 데이트를 주선할 수 없다. 요약하면, 주어진 정보를 바탕으로, Anne은 각 데이트가 선호 상대 목록에 있는 쌍일 때에만 성사되고, 각 학생의 예정된 데이트 횟수가 각자의 최소 및 최대 기대치 안에 있도록 IC와 PC 학생 사이의 데이트를 주선해야 한다. Anne이 세 가지 제약을 모두 만족시키면서 주선할 수 있는 최대 데이트 횟수를 구하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 읽는다. 입력은 세 정수 m, n, k (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)를 포함하는 한 줄로 시작한다. 여기서 m은 IC 학교 학생 수, n은 PC 학교 학생 수, k는 선호 상대 목록의 수이다. IC 학교의 각 학생에게는 1부터 m까지의 고유한 번호가 주어지고, PC 학교의 각 학생에게는 1부터 n까지의 고유한 번호가 주어진다. 이 고유한 번호가 학생 ID이다. 두 번째 줄에는 m개의 음이 아닌 정수가 있으며, 각각 i번째 IC 학생의 최소 기대 데이트 횟수이다. 세 번째 줄에는 m개의 음이 아닌 정수가 있으며, 각각 i번째 IC 학생의 최대 기대 데이트 횟수이다. 마찬가지로, 네 번째 줄에는 PC 학생의 최소 기대 데이트 횟수를 나타내는 n개의 음이 아닌 정수가 있고, 다섯 번째 줄에는 PC 학생의 최대 기대 데이트 횟수를 나타내는 n개의 음이 아닌 정수가 있다. 각 학생의 최소 및 최대 데이트 횟수는 0 이상이며, IC 학생은 최대 n, PC 학생은 최대 m이다. 다음 k개의 줄에서 각 줄은 두 학생 ID를 포함하며, 첫 번째는 IC 학생의 ID이고 두 번째는 그 IC 학생이 선호하는 PC 학생 ID이다.

프로그램은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 그 줄은 Anne이 주선할 수 있는 최대 데이트 횟수를 포함해야 한다. Anne이 세 가지 제약을 모두 만족하는 데이트 일정을 주선할 수 없다면, -1을 출력한다.