题目详情
返回题库题目描述
AtCoder自助餐厅出售由主菜和配菜组成的餐点。
主菜有N种，称为主菜1，主菜2，…，主菜N。主菜i的价格为ai元
配菜有M种，称为配菜1，配菜2，…，配菜M。配菜i的价格是bi元
套餐是由选择一道主菜和一道配菜组成的。套餐的价格是所选主菜和配菜的价格之和。然而，对于L个组合（c1 ,d 1 ),…,（cL ,dL ),由主菜ci组成的套餐配配菜di，这个L个搭配套餐没有办法提供，因为他们在组合在一起让人无法忍受。
也就是说，提供N*M−L份套餐。（限制条件保证至少能提供一份套餐。）找出最贵套餐的价格。
输入描述
输入格式
N,M,L
a1,a2,a3.......an
b1,b2,b3.......bm
c1 d1
c2 d2
c3 d3
c4 d4
......
cl dl
数据范围：
- 1≤N,M≤10^5
- 0≤L≤min(10^5,N*M−1)
- 1≤ai,bi≤10^9
- 1≤ci≤N
- 1≤dj≤M
- (ci,di)!=(cj,dj) ifi!=j.
输出描述
输出提供的套餐中最贵的一个组合的价格