#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define flow(from,to) (f[from][to] - f[to][from]) #define residue(from,to) (cap[from][to] - flow(from,to)) int cap[512][512]; int f[512][512]; typedef int V; int d[512][512]; int dr[512][512]; int buf[512][512]; void wf( int N ) { for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ){ dr[i][j] = d[i][j]; } for( int i = 0; i < N; i ++ ){ dr[i][i] = 0; } for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ) buf[i][j] = dr[i][j]; for( int k = 0; k < N; k ++ ){ for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ){ if( dr[i][k] >= 0 && dr[k][j] >= 0 ){ int dd = dr[i][k] + dr[k][j]; if( dr[i][j] < 0 || dr[i][j] > dd ) buf[i][j] = dd; } } for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ) dr[i][j] = buf[i][j]; } } V mf( int s, int t, int n ) { int prev[512]; for( int i = 0; i < n; i ++ ) for( int j = 0; j < n; j ++ ) f[i][j] = 0; V flow_sum = 0; while( 1 ){ queue q; for( int i = 0; i < n; i ++ ) prev[i] = -1; prev[s] = -2; q.push( s ); while( !q.empty() && prev[t] == -1 ){ int pos = q.front(); q.pop(); for( int i = 0; i < n; ++ i ){ if( prev[i] == -1 && residue(pos,i) > 0 ){ prev[i] = pos; q.push( i ); } } } if( prev[t] == -1 ) return flow_sum; V r = -1; for( int i = t; prev[i] >= 0; i = prev[i] ){ V res = residue(prev[i], i); if( r < 0 || res < r ) r = res; } // printf( "%d %d\n", flow_sum, r ); if( r > 0 ){ for( int i = t; prev[i] >= 0; i = prev[i] ){ f[prev[i]][i] += r; } flow_sum += r; } } } int main( void ) { FILE *in = fopen( "nucleus.in", "r" ); while( 1 ){ int N, M, L; fscanf( in, "%d%d%d", &N,&M, &L ); if( feof( in ) ) break; for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ) d[i][j] = L + 1; // d[i][0] = 0; for( int i = 0; i < M; i ++ ){ int a, b, D; fscanf( in, "%d%d%d", &a, &b, &D ); a -- , b --; d[a][b] = D; d[b][a] = D; } wf( N ); // printf( "wf\n" ); int n2 = N * 2 + 2; for( int i = 0; i < n2; i ++ ) for( int j = 0; j < n2; j ++ ) cap[i][j] = 0; for( int i = 0; i < N; i ++ ) for( int j = 0; j < N; j ++ ) if( dr[i][j] < L ) cap[i + 2][j + 2 + N] = 100000000; for( int i = 0; i < N; i ++ ){ int k; fscanf( in, "%d", &k ); cap[0][2 + i] = k; } for( int i = 0; i < N; i ++ ){ int k; fscanf( in, "%d", &k ); cap[2 + N + i][1] = k; } printf( "%d\n", mf( 0, 1, n2 ) ); } return 0; }