#include<bits/stdc++.h>
using namespace std;
const int maxn = 105, maxm = 10000005, INF = 2147483647;
int head[maxn<<2], ver[maxm], edge[maxm], Next[maxm], tot;
void add(int x,int y,int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
int n, p, q;
int s, t, maxflow, incf[maxn<<2], pre[maxn<<2];bool vis[maxn<<2];
bool bfs()
{
for(int i=1; i<=n+p+q+n+2; i++) vis[i] = false;
queue<int> Q;
Q.push(s), vis[s] = true, incf[s] = INF;
while(!Q.empty())
{
int x = Q.front(); Q.pop();
for(int i=head[x]; i; i=Next[i])
if(edge[i])
{
int y = ver[i];
if(vis[y]) continue;
incf[y] = min(incf[x], edge[i]), pre[y] = i;
vis[y] = true;
if(y == t) return true;
Q.push(y);
}
}
return false;
}
void update()
{
int x = t;
while(x!=s)
{
int i = pre[x];
edge[i] -= incf[t];
edge[i^1] += incf[t];
x = ver[i^1];
}
maxflow+=incf[t];
}
int main()
{
tot = 1;
scanf("%d%d%d",&n,&p,&q);
s = n+p+q+n+1, t = n+p+q+n+2;
for(int i=1; i<=n; i++)
for(int j=1; j<=p; j++)
{
bool x;
scanf("%d",&x);
if(x) add(j+n, i, 1);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=q; j++)
{
bool x;
scanf("%d",&x);
if(x) add(i+n+p+q, j+n+p, 1);
}
for(int i=1; i<=p; i++) add(s, i+n, 1);
for(int i=1; i<=q; i++) add(i+n+p, t, 1);
for(int i=1; i<=n; i++) add(i, i+n+p+q, 1);
while(bfs()) update();
printf("%d", maxflow);
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=6e4;
int n,m,t,tot=0,atot=0,btot=0,ctot=0;
int d[N],query[N],f[N][20];
int ver[2*N],edge[2*N],Next[2*N],head[N];
bool ok,sta[N],need[N];
ll ans,tim[N],ned[N],dist[N][20];
pair<ll,int> h[N];
queue<int> q;
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(d[y])
continue;
d[y]=d[x]+1;
f[y][0]=x,dist[y][0]=edge[i];
for(int j=1;j<=t;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
dist[y][j]=dist[y][j-1]+dist[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
bool dfs(int x)
{
bool pson=0;
if(sta[x])
return 1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(d[y]<d[x])
continue;
pson=1;
if(!dfs(y))
return 0;
}
if(!pson)
return 0;
return 1;
}
bool check(ll lim)
{
memset(sta,0,sizeof(sta));
memset(tim,0,sizeof(tim));
memset(ned,0,sizeof(ned));
memset(h,0,sizeof(h));
memset(need,0,sizeof(need));
atot=0,btot=0,ctot=0;
for(int i=1;i<=m;i++)
{
ll x=query[i],cnt=0;
for(int j=t;j>=0;j--)
if(f[x][j]>1 && cnt+dist[x][j]<=lim)
{
cnt+=dist[x][j];
x=f[x][j];
}
if(f[x][0]==1 && cnt+dist[x][0]<=lim)
h[++ctot]=make_pair(lim-cnt-dist[x][0],x);
else
sta[x]=1;
}
for(int i=head[1];i;i=Next[i])
if(!dfs(ver[i]))
need[ver[i]]=1;
sort(h+1,h+ctot+1);
for(int i=1;i<=ctot;i++)
if(need[h[i].second] && h[i].first<dist[h[i].second][0])
need[h[i].second]=0;
else
tim[++atot]=h[i].first;
for(int i=head[1];i;i=Next[i])
if(need[ver[i]])
ned[++btot]=dist[ver[i]][0];
if(atot<btot)
return 0;
sort(tim+1,tim+atot+1),sort(ned+1,ned+btot+1);
int i=1,j=1;
while(i<=btot && j<=atot)
if(tim[j]>=ned[i])
{
i++,j++;
}
else
j++;
if(i>btot)
return 1;
return 0;
}
int main()
{
ll l=0,r=0,mid;
cin>>n;
t=log2(n)+1;
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
r+=z;
}
bfs();
cin>>m;
for(int i=1;i<=m;i++)
scanf("%d",&query[i]);
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
ok=1;
}
else
l=mid+1;
}
if(!ok)
cout<<-1;
else
cout<<ans;
return 0;
}