Get Maximum Cost (Subscription Plan)

Choose one plan and one feature; the given incompatible index pairs cannot be chosen. At least one compatible combination exists; find the maximum total price.

输入格式

The first line contains n m X; 2≤n,m≤100000, 1≤X≤min(200000,nm−1); then two lines of price arrays (1..10⁹); followed by X lines of incompatible pairs, numbered from 1.

输出格式

Output a single integer answer.

样例 1

输入：

2 2 1
5 8
4 7
2 2

输出：

12

样例 2

输入：

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

输出：

6

样例 3

输入：

2 2 1
9 1
8 1
2 2

输出：

17

样例说明

Example 1: 8+4 and 5+7 both give 12; 8+7 is forbidden. Example 2: only plan 2 and feature 2 can be paired, for a total price of 6. Example 3: the highest pair 9+8 is allowed, for a total price of 17.