记录编号	351233	评测结果	WWTEEEEEEE
题目名称	冰桥，升起来了！	最终得分	0
用户昵称	Hoohan(%Dalao)	是否通过	未通过
代码语言	C++	运行时间	1.538 s
提交时间	2016-11-16 12:15:30	内存使用	0.47 MiB

//meibridge.cpp
//By Hoohan
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
using namespace std;

int a,b,k;
const int maxa=400,maxb=400,maxk=100010;
int va[maxa],vb[maxb];
int ansa[maxa],ansb[maxb];//向下走的最大值 
bool tu[maxa][maxb];

int bfs(int last,int now,bool side) //side=0 in A side=1 in B
{
//	cout<<"last,now,side"<<last<<' '<<now<<' '<<side<<endl;
	if(last==b && side==0 && now==a) return va[a];
	if(last==a && side==1 && now==b) return vb[b];
	if(side==0){
		for(int i=last+1;i<=b;i++)
		{
			if(tu[now][i]==1) 
			{
				ansa[now]=max(ansa[now],bfs(now,i,1)+va[i]);
			}
		}
		return ansa[now];
	}
	else{
		for(int i=last+1;i<=a;i++)
		{
			if(tu[i][now]==1) 
			{
				ansb[now]=max(ansb[now],bfs(now,i,0)+vb[i]);
			}
		}
		return ansb[now];
	}
}

int main()
{
	freopen("meibridge.in","r",stdin);
	freopen("meibridge.out","w",stdout);
	memset(ansa,0,sizeof(ansa));
	memset(ansb,0,sizeof(ansb));
//	memset(ansa,0,sizeof(ansa));
//	memset(ansa,0,sizeof(ansa));
	cin>>a>>b>>k;
	for(int i=1;i<=a;i++) cin>>va[i];
	for(int i=1;i<=b;i++) cin>>vb[i];
	/*
	for(int i=1;i<=a;i++) cout<<va[i]<<' ';
	cout<<endl;
	for(int i=1;i<=b;i++) cout<<vb[i]<<' ';
	cout<<endl;
	*/
	int x,y;
	for(int i=1;i<=k;i++)
	{
		cin>>x>>y;
		tu[x][y]=1;
	//	tu[y][x]=1;
	}
	for(int i=1;i<a;i++)
	bfs(0,i,0);
	for(int i=1;i<b;i++)
	bfs(0,i,1);
	sort(ansa+1,ansa+a+1);
	sort(ansb+1,ansb+b+1);
//	for(int i=1;i<=a;i++) cout<<ansa[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<=b;i++) cout<<ansb[i]<<' ';
//	cout<<endl;
	cout<<max(ansa[a],ansb[b]);
	return 0; 
}