题目描述

上午的课程结束了，于是又到了安东诺夫最喜欢的午饭环节。

位于阿尔巴特大街上的彼得罗夫餐厅有 $N$ 种主菜和 $M$ 种副食，它们都有自己的价格。

安东诺夫每次吃饭的时候都会点一种主菜和一种副食，然后享受一顿美妙的午饭。

但是并不是所有的组合都是他喜欢的。这 $NM$ 种组合当中有 $L$ 种是他极其讨厌的，他一定不会点这些组合。

现在他想知道他的每顿午饭最贵的价格是多少。

输入格式

第一行为三个整数 $N,M,L$。

第二行为 $N$ 种主菜的价格。

第三行为 $M$ 种副食的价格。

最后 $L$ 行为安东诺夫不喜欢的组合，其中第一个数表示这个组合中的主菜，第二个数表示这个组合中的副食。

输入保证最后安东诺夫一定能有吃的。

输出格式

一个数，为安东诺夫午饭的最贵价格。

2 3 3
2 1
10 30 20
1 2
2 1
2 3

31

2 1 0
1000000000 1
1000000000

2000000000

10 10 10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
7017 46004 16086 62644 74928 57404 32168 45794 19493 71590
1 3
2 6
4 5
5 4
5 5
5 6
5 7
5 8
5 10
7 3

149076

数据范围

• $1\ \leq\ N,\ M\ \leq\ 10^5$
• $0\ \leq\ L\ \leq\ \min(10^5,\ N\times \ M\ -\ 1)$
• 每道主菜和副食的价格都小于等于 $10^9$
• 组合间保证不会互相重复