Problem: Year 20XX — a nuclear explosion has burned the world. Half the people on the planet have died. Fearful.

One city, fortunately, was not directly damaged by the explosion. This city consists of N domes (numbered 1 through N inclusive) and M bidirectional transportation pipelines connecting the domes. In dome i, Pi citizens reside currently and there is a nuclear shelter capable of protecting Ki citizens. Also, it takes Di days to travel from one end to the other end of pipeline i.

It has been turned out that this city will be polluted by nuclear radiation in L days after today. So each citizen should take refuge in some shelter, possibly traveling through the pipelines. Citizens will be dead if they reach their shelters in exactly or more than L days.

How many citizens can survive at most in this situation?



Input

The input consists of multiple test cases. Each test case begins with a line consisting of three integers N, M and L (1 ≤ N ≤ 100, M ≥ 0, 1 ≤ L ≤ 10000). This is followed by M lines describing the configuration of transportation pipelines connecting the domes. The i-th line contains three integers Ai, Bi and Di (1 ≤ Ai < Bi ≤ N, 1 ≤ Di ≤ 10000), denoting that the i-th pipeline connects dome Ai and Bi. There is at most one pipeline between any pair of domes. Finally, there come two lines, each consisting of N integers. The first gives P1 , . . ., PN (0 ≤ Pi ≤ 106) and the second gives K1 , . . ., KN (0 ≤ Ki ≤ 106).

The input is terminated by EOF. All integers in each line are separated by a whitespace.

Output

For each test case, print in a line the maximum number of people who can survive.

Example

Input

1 0 1
51
50
2 1 1
1 2 1
1000 0
0 1000
4 3 5
1 2 4
1 3 1
3 4 2
0 1000 1000 1000
3000 0 0 0


Output

50
0
3000

Solution (in CPP):

Solution:
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) cerr << #x << "=" << static_cast<bitset<16> >(x) << endl;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 100000000;
typedef double D;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem2076 : Flame of Nucleus **/
const int MAX_V = 300;

int d[MAX_V][MAX_V];
int V;


class Flow {
public:
	struct edge { int to, cap, rev, cost;};
	vector<edge> G[MAX_V];
	bool used[MAX_V];
	int V;
	
	int dist[MAX_V];
	int prevv[MAX_V], preve[MAX_V];
	
	Flow() {V=MAX_V;}
	Flow(int v) {
		V = v;
	}
	
	void add_edge(int from, int to, int cap) {
		G[from].push_back((edge){to, cap, (int)G[to].size(), 0});
		G[to].push_back((edge){from, 0, (int)G[from].size()-1, 0});
	}
	
	void add_edge_with_cost(int from, int to, int cap, int cost) {
		G[from].push_back((edge){to, cap, (int)G[to].size(), cost});
		G[to].push_back((edge){from, 0, (int)G[from].size()-1, -cost});
	}
	
	// 最大流
	int dfs(int v, int t, int f) {
		if (v==t) return f;
		used[v] = true;
		for (int i=0; i<G[v].size(); i++) {
			edge &e = G[v][i];
			if (!used[e.to] && e.cap>0) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d>0) {
					e.cap-=d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	
	int max_flow(int s, int t) {
		int flow = 0;
		for (;;) {
			memset(used, 0, sizeof(used));
			int f = dfs(s, t, INF);
			if (f==0) return flow;
			flow += f;
		}
	}
	
	// 最小費用流
	int min_cost_flow(int s, int t, int f) {
		int res=0;
		while (f>0) {
			fill(dist, dist+V, INF);
			dist[s]=0;
			bool update=true;
			while (update) {
				update = false;
				for (int v=0; v<V; v++) {
					if (dist[v]==INF) continue;
					for (int i=0; i<G[v].size(); i++) {
						edge &e = G[v][i];
						if (e.cap>0 && dist[e.to] > dist[v] + e.cost) {
							dist[e.to] = dist[v] + e.cost;
							prevv[e.to] = v;
							preve[e.to] = i;
							update = true;
						}
					}
				}
			}
			
			if (dist[t] == INF) {
				return -1;
			}
			
			int d=f;
			for (int v=t; v!=s; v=prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*dist[t];
			for (int v=t; v!=s; v=prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}
};

void warshall_floyd()
{
	rep(k, V) {
		rep(i, V) {
			rep(j, V) {
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}
}

int main()
{
	int N, M, L;
	while (cin>>N>>M>>L) {
		V = N;
		
		fill(d[0], d[0]+MAX_V*MAX_V, INF);
		rep(i, M) {
			int a, b, c; cin>>a>>b>>c;
			d[a-1][b-1] = d[b-1][a-1] = c;
		}
		rep(i, MAX_V) {
			d[i][i] = 0;
		}
		
		warshall_floyd();
		
		Flow F(2*N+2);
		rep(i, N) {
			rep(j, N) {
				if (d[i][j] < L) {
					F.add_edge(i, N+j, INF);
				}
			}
		}
		rep(i, N) {
			int a; cin>>a;
			F.add_edge(2*N, i, a);
		}
		rep(i, N) {
			int a; cin>>a;
			F.add_edge(N+i, 2*N+1, a);
		}
		
		cout << F.max_flow(2*N, 2*N+1) << endl;
	}
}