#include #include #include using namespace std; void Quick_Read(int &N) { N = 0; char c = getchar(); int op = 1; while(c < '0' || c > '9') { if(op == '-') op = -1; c = getchar(); } while(c >= '0' && c <= '9') { N = (N << 1) + (N << 3) + c - 48; c = getchar(); } N *= op; } const int MAXN = 1e2 + 5; const int MAXM = 2e3 + 5; int dp[MAXN][MAXN][MAXM]; int A[MAXN], B[MAXN], P[MAXN], Q[MAXN]; int n, m, k, c; int sum; void Read() { Quick_Read(n); Quick_Read(m); Quick_Read(k); Quick_Read(c); for(int i = 1; i <= n; i++) Quick_Read(A[i]); for(int i = 1; i <= n; i++) Quick_Read(B[i]); for(int i = 1; i <= m; i++) { Quick_Read(P[i]); Quick_Read(Q[i]); sum += B[P[i]] + B[Q[i]]; } } void DP() { memset(dp, 128, sizeof(dp)); for(int i = 0; i <= m; i++) dp[i][0][0] = 0; for(int i = 1; i <= m; i++) { for(int l = 1; l <= i; l++) { for(int j = 0; j <= sum; j++) { dp[i][l][j] = max(dp[i][l][j], dp[i - 1][l][j]); if(j - B[P[i]] - B[Q[i]] >= 0) dp[i][l][j] = max(dp[i - 1][l][j], dp[i - 1][l - 1][j - B[P[i]] - B[Q[i]]] + A[P[i]] * A[Q[i]]); } } } int ans = -1; for(int i = c; i <= sum; i++) ans = max(ans, dp[m][k][i]