어느 학교에 학생 \(N\)명과 방과후 강좌 \(M\)개가 있다. 강좌 \(j\)의 정원은 \(c_j\)명이다. 정원이 \(0\)인 강좌는 폐강되어 아무도 들을 수 없다.

학생들은 각각 듣고 싶은 강좌 목록을 제출했다.

한 학생은 강좌를 최대 하나만 들을 수 있고, 강좌 \(j\)에는 학생이 최대 \(c_j\)명까지 들어갈 수 있다.

학생은 자신이 희망한 강좌에만 배정될 수 있다.

강좌에 배정되는 학생 수의 최댓값을 구하시오.

입력

첫째 줄에 학생 수 \(N\), 강좌 수 \(M\), 희망 정보의 개수 \(K\)가 공백으로 구분되어 주어진다.

둘째 줄에 각 강좌의 정원 \(c_1, c_2, \dots, c_M\)이 공백으로 구분되어 주어진다.

셋째 줄부터 \(K\)개의 줄에 걸쳐 두 정수 \(a\)와 \(b\)가 공백으로 구분되어 주어진다.

이는 학생 \(a\)가 강좌 \(b\)를 희망한다는 뜻이다.

출력

강좌에 배정될 수 있는 학생 수의 최댓값을 출력한다.

제한 사항

• \(1 \le N, M \le 500\)
• \(0 \le c_j \le 5\)
• \(0 \le K \le 10,000\)
• \(1 \le a \le N\)
• \(1 \le b \le M\)
• 같은 \((a, b)\) 쌍은 두 번 이상 주어지지 않는다.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

3 3 4
1 0 2
1 2
2 1
2 3
3 1

예제 출력 2

2

노트

예제 1에서 강좌 1의 정원은 \(2\)명, 강좌 2의 정원은 \(1\)명이므로 최대 \(3\)명까지 배정할 수 있다.

예를 들어 학생 2, 3을 강좌 1에, 학생 1을 강좌 2에 배정하면 \(3\)명이 배정된다.

예제 2에서 학생 1은 폐강된 강좌 2만 희망하므로 배정될 수 없다.

학생 2를 강좌 3에, 학생 3을 강좌 1에 배정하면 \(2\)명이 배정된다.