In Byteland we can study only math and IT.

In the university there are n math students and m IT students.

Rector Byteasar knows IQ of every student. He wants to make the best team, which would solve the hardest human being problems. So he decided to pick team with the highest summary IQ.

Of course it's not everything. He wants to make team in which each student knows another students from team.

Every student from IT know other student from IT and same with math students.

Help him finding team with the largest summary IQ and in which every student from team knows another students from team.

Input

In first line n, m, k (0 < n ≤ 400, 0 < m ≤ 400, 0 ≤ k ≤ n × m) which means number of math students, number of IT students, number of friendships between IT and math student.

In next k lines pairs

0 < ai ≤ n, 0 < bi ≤ m, which means ai student from math knows bi student from IT.

In next line n numbers, IQ of i-th math student.

In next line m numbers, IQ of i-th IT student.

Output

Output in one line : number of team's summary IQ.

Example

Input:
3 2 3
1 1
2 1
2 2
1 3 1
1 2

Output:
6