RT，虽然应该也没人会回复/ll

建图方式是对每个点拆成 $in,out$。

下文用 $(a,b,c,d)$ 表示 $a\to b$ 有一条容量 $c$，花费 $d$ 的边。

对于每条边 (x_out,y_in,inf,0)
每个点 (x_in,x_out,1,-valx) (x_in,x_out,inf,0)
(x_out,T,inf,0) (S,1_in,K,0)

观察到有负权，可能产生负环，所以我 rush 了个【模板】有负圈的费用流。

但是还是过不了样例 1，交上去是 AC 27 个点，WA 2 个点，TLE 8个点。

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
/*
拆点，入、出
对于每条边 (x_out,y_in,inf,0)
每个点 (x_in,x_out,1,-valx) (x_in,x_out,inf,0)
(x_out,T,inf,0) (S,1_in,K,0)
*/
#define N (int)(4e6+5)
#define inf (int)(2e16)
struct edge {
	int nex,to,w,c;
}e[N<<1];
int hea[N],cnt=1;
int n,m,K,S,T,answ,tot,s,t,ansf;

void add_edge(int x,int y,int z,int c) {
	e[++cnt].nex=hea[x]; e[cnt].to=y; e[cnt].w=z; e[cnt].c=c; hea[x]=cnt;
}

void add(int x,int y,int z,int c) {
	add_edge(x,y,z,c); add_edge(y,x,0,-c);
}

deque<int>q;
int dis[N];
bool vis[N];
bool spfa() {
	for(int i=0;i<=tot;i++) dis[i]=inf,vis[i]=0;
	dis[S]=0; q.push_back(S);
	while(!q.empty()) {
		int x=q.front(); q.pop_front();
		vis[x]=0;
		for(int i=hea[x];i;i=e[i].nex) {
			int y=e[i].to;
			if(e[i].w>0&&dis[y]>dis[x]+e[i].c) {
				dis[y]=dis[x]+e[i].c;
				if(!vis[y]) {
					vis[y]=1;
					if(!q.empty()&&dis[y]<dis[q.front()]) q.push_front(y);
					else q.push_back(y);
				}
			}
		}
	}
	//cout<<dis[T]<<'\n';
	return dis[T]<inf;
}

int dfs(int x,int lim) {
	if(x==T||lim<=0) return lim;
	vis[x]=1;
	int flow=0,fl;
	for(int i=hea[x];i&&lim;i=e[i].nex) {
		int y=e[i].to;
		if(e[i].w>0&&!vis[y]&&dis[y]==dis[x]+e[i].c) {
			fl=dfs(y,min(lim,e[i].w));
			if(fl<=0) continue;
			flow+=fl; lim-=fl; e[i].w-=fl; e[i^1].w+=fl; answ+=fl*e[i].c; 
//			cout<<answ<<" "<<x<<" "<<y<<" "<<fl<<" "<<e[i].c<<'\n';
		}	
	} 
	if(flow<=0) dis[x]=inf;
	vis[x]=0;
	return flow;
}
 
void zkw() {
	while(spfa()) {
		memset(vis,0,sizeof(bool)*(tot+1));
		//cout<<"mmm\n";
		ansf+=dfs(S,inf);
	}
}
int d[N];
signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>n>>m>>K; s=0; t=2*n+1; S=2*n+2; T=tot=2*n+3;
	for(int i=1;i<=m;i++) {
		int x,y; cin>>x>>y;
		add(x+n,y,inf,0);
	} 
	for(int i=1;i<=n;i++) {
		int x; cin>>x;
//		add(i,i+n,1,-x); 
		answ-=x;
		d[i]--; d[i+n]++;
		add(i+n,i,1,x);
		add(i,i+n,inf,0);
		add(i+n,t,inf,0);
	}
	d[s]-=K; d[1]+=K;
	add(t,s,inf,0);
	for(int i=0;i<=2*n+1;i++) {
		if(d[i]>0) add(S,i,d[i],0); else if(d[i]<0) add(i,T,-d[i],0);
	}
	zkw(); 
	for(int i=hea[t];i;i=e[i].nex) {
		if(e[i].to==s) {
			e[i].w=e[i^1].w=0; break;
		}
	}
	ansf=0; S=s; T=t; zkw(); 
	cout<<-answ;
	return 0;
}