There is an  grid, some positions of it contain non-negative integers , while others contain nothing.

Now, given an empty number grid, and some positions of it (those positions must contain a non-negative integer, while others must contain nothing), and the maximum value of  in each row , the maximum value of  in each column , you need to find a way to fill non-negative integers in the grid in order to satisfy those conditions.

Since there are many possible ways, you are asked to find the minimum value of ,a.k.a the sum of numbers in this grid.
It's guaranteed that there exists a way to fill non-negative integers in the grid in order to satisfy those conditions.

输入描述:

The first line of the input contains three integers n,m,k, denoting the size of the grid, the total number of positions available to contain integers, and the maximum value of all constraints in the number grid; Remember that you don't need to make the maximum value of all numbers in the number grid actually k.
The second line of the input contains n integers .
The third line of the input contains n integers .
It is guaranteed that there doesn't exist an integer appearing  times among all the .
The next m lines of the input contains two integers x,y each, denoting a position .

输出描述:

The only line of the output contains an integer S, denoting the minimum value of . available to contain an integer.

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

22

- - - - 1
- - - 2 -
- - 3 - 0
- 2 - - 4
1 - 0 4 5

4 10 7
3 6 2 6
5 6 6 3
1 1
1 4
2 2
2 3
2 4
3 2
4 1
4 2
4 3
4 4

22

0 - - 3
- 6 0 0
- 2 - -
5 0 6 0

备注: