提供一种简单的线段树写法。

首先，给出朴素的 DP，令 dpi,jdp_{i,j} 表示前 ii 种食物，第 ii 种选择了 jj 的最小花费，显然得出转移：

dpi,j=min⁡(j,k) is OKdpi−1,k+ci,jdp_{i,j}=\min\limits_{\text{(j,k)\ is\ OK}}dp_{i-1,k}+c_{i,j}

边界：

dp1,i=c1,idp_{1,i}=c_{1,i}

接下来将取最小值的枚举优化，一种简单的想法是，以 dpi−1dp_{i-1} 建立线段树，每次枚举 kk 时，将所有不符合条件的数字设置为正无穷，处理完这个 jj 之后再将修改复原，这样的均摊时间复杂度为 O(nlog⁡n)O(n\log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define int long long
using namespace std;
template <typename T> struct SegmentTree{struct node{int l,r;T v,tag;}t[2000006*4];T dat[2000006];void pushup(int x){t[x].v=op(t[x*2].v,t[x*2+1].v);}void build(int x,int l,int r){t[x].l=l;t[x].r=r;if(l==r){t[x].v=dat[l];return;}int mid=(l+r)/2;build(x*2,l,mid);build(x*2+1,mid+1,r);pushup(x);}void pushdown(int x){if(t[x].tag&&t[x].l!=t[x].r){apply(x*2,t[x].tag);apply(x*2+1,t[x].tag);t[x].tag=0;}}void update(int x,int L,int R,T v){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){apply(x,v);return;}pushdown(x);int mid=(l+r)/2;if(L<=mid)update(x*2,L,R,v);if(mid+1<=R)update(x*2+1,L,R,v);pushup(x);}T query(int x,int L,int R){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){return t[x].v;}pushdown(x);int mid=(l+r)/2;T tot=tot_init;if(L<=mid)tot=q_op(tot,query(x*2,L,R));if(mid+1<=R)tot=q_op(tot,query(x*2+1,L,R));return tot;}
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return min(x,y);}
        T q_op(T x,T y){return min(x,y);}
        T tot_init=0x3f3f3f3f;
        void apply(int x,T v){
            t[x].v=v;
            t[x].tag=v;
        }
    ////////////////// 自定义函数区 ///////////////////
};//区间最小值板子
SegmentTree<int>SegTree;
int n[5];
int a[5][200005];
int dp[5][200005];
int m[5];
int bx[5][200005];
int by[5][200005];
vector<int>nok[5][200005];
//nok记录不可用的点对
void solve(){
	for(int i=1;i<=4;i++){
		scanf("%lld",&n[i]);
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=n[i];j++){
			scanf("%lld",&a[i][j]);
		}
	}
	for(int i=2;i<=4;i++){
		scanf("%lld",&m[i]);
		for(int j=1;j<=m[i];j++){
			scanf("%lld%lld",&bx[i][j],&by[i][j]);
			nok[i][by[i][j]].push_back(bx[i][j]);
		}
	}
	for(int i=1;i<=n[1];i++){
		dp[1][i]=a[1][i];
	}
	for(int i=2;i<=4;i++){
		for(int j=1;j<=n[i]*4;j++){
			SegTree.t[j].v=SegTree.t[j].tag=0;
			SegTree.t[j].l=SegTree.t[j].r=0;
		}
		for(int j=1;j<=n[i-1];j++){
			SegTree.dat[j]=dp[i-1][j];
		}
		SegTree.build(1,1,n[i-1]);
		for(int j=1;j<=n[i];j++){
			for(auto k:nok[i][j]){
				SegTree.update(1,k,k,0x3f3f3f3f);
			}
			dp[i][j]=SegTree.query(1,1,n[i-1])+a[i][j];
			for(auto k:nok[i][j]){
				SegTree.update(1,k,k,dp[i-1][k]);
			}
		}
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n[4];i++){
		ans=min(ans,dp[4][i]);
	}
	if(ans==0x3f3f3f3f){
		printf("-1\n");
	}
	else{
		printf("%lld\n",ans);
	}
}
signed main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	cerr<<"[File IO]"<<endl;
#endif
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}