#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int dp[1001][101];

int main()
{
	int L,N,M,X;
	while(cin >> L >> N >> M >> X, (L||N||M||X)) {
		vector<pair<int, int> > secret(N);
		vector<pair<int, int> > normal(M);
		for(int i=0; i<N; i++) {
			string n;
			int e,s;
			cin >> n >> e >> s;
			secret[i] = make_pair(e, s);
		}

		for(int i=0; i<M; i++) {
			string n;
			int e,s;
			cin >> n >> e >> s;
			normal[i] = make_pair(e, s);
		}

		memset(dp, -1, sizeof(dp));
		for(int i=0; i<N; i++) 
		for(int j=i+1; j<N; j++) {
			int l = secret[i].first, r = secret[j].first;
			if(l <= L) dp[l][0] = max(dp[l][0], secret[i].second);
			if(r <= L) dp[r][0] = max(dp[r][0], secret[j].second);

			if(l + r <= L) dp[l + r][0] = max(dp[l + r][0], secret[i].second + secret[j].second);
		}

		for(int i=0; i<M; i++)
		for(int j=i; j>=0; j--) {
			int c = normal[i].first;
			int s = normal[i].second;

			for(int k=0; k<=L; k++) {
				if(dp[k][j] == -1) continue;
				if(k + c > L) break;

				dp[k + c][j + 1] = max(dp[k + c][j + 1], dp[k][j] + s);
			}
		}

		int res = 0;

		for(int i=0; i<=L; i++)
		for(int j=X; j<=M; j++)
			res = max(res, dp[i][j]);

		cout << res << endl;
	}
}