题目描述

Sophia 厌倦了法术世界唯实力主义的生活。

她打算回到凡间种玫瑰，于是她种了一片巨大的 $n \times n$ 的玫瑰田，然后借助雨水的浇灌让这些玫瑰自然成长。

然而雨很调皮，会首先按行浇灌，然后按列浇灌，另外有些地形不适合种玫瑰。

她很累了，所以想种的玫瑰数量尽量少。

通俗地来说，给定一个 $n \times n$ 的矩阵和一些可以填数的格子，请你在这些格子里面填正整数，要求这些正整数每行每列的最大值是给定值，求正整数之和的最小值。

输入格式

第一行三个正整数 $n, m, k$，其中 $k$ 表示所有限定数中的最大值。

第二行 $n$ 个整数，从上到下表示每一行的限定数。

第三行 $n$ 个整数，从左到右表示每一列的限定数。

之后的 $m$ 行每行两个整数，表示一个可以种玫瑰的位置的坐标。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

3 9 1
1 1 1
1 1 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

4

样例 #3

样例输入 #3

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

样例输出 #3

22

数据范围

$n \leq 2500$