#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)x)<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define EREP(i,a,b) for(int i=a;i<=b;i++)
#define erep(i,n) EREP(i,0,n)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

int limit,n,m,x; //ãÀz, V[Nbgl, Êíl, ÊíÌÅál
int sec_e[102],sec_s[102],e[102],s[102]; //V[NbgÌÙpàE«x, ÊíÌÙpàE«x
int sec[1002]; //cèàª i ÌÆ«ÌÅ«xÍ sec[i]
short dp[102][102][1002]; //dp[i][j][k] = iÔÌA[eBXgÜÅÅ, jlIñ¾Æ«, kÌïpðgpµÄ, ¾éÅå«x

int main(void){
  while(cin>>limit>>n>>m>>x,limit||n||m||x){
    rep(i,n){
      string tmp;
      cin>>tmp>>sec_e[i]>>sec_s[i];
    }
    rep(i,m){
      string tmp;
      cin>>tmp>>e[i]>>s[i];
    }

    //V[Nbg©ç, 1l or 2lðIñÅ¢­
    //s¾l-1Å é
    memset(sec,-1,sizeof(sec));
    rep(i,n){ //1lÚ
      REP(j,i,n){ //2lÚ
        int money,satis; //Kvàz, «x

        if(i == j){ //1lIÔê
          money = sec_e[i];
          satis = sec_s[i];
        }
        else{ //2lIÔê
          money = sec_e[i] + sec_e[j];
          satis = sec_s[i] + sec_s[j];
        }
        if(money > limit) continue; //àµ, limitæèÙpàªå«¢ÈçÎcontinue

        //àÌcèªmoneyÅ éÆ«É¾çêé«xÌÅålðÆé
        sec[money] = max(sec[money],satis);
      }
    }

    //cèàª, iuÈºvÅ éÆ«É¾çêéÅå«xÉÈéæ¤Éseczñð«Ï¦
    REP(i,1,limit+1) sec[i] = max(sec[i],sec[i-1]);

    //DPzñÌú». s¾l-1
    memset(dp,-1,sizeof(dp));
    dp[0][0][0] = 0; //úl=0

    rep(i,m){ //iÔÚÌA[eBXgÜÅÅl¦é
      rep(j,i+1){ //»êÜÅÉjlÌA[eBXgðIñ¾Æ«ii+2lÈãÍIñÅéÍ¸ªÈ¢©ç³j
        rep(k,limit+1){ //àðkgpµ½Æ«(kÍ, limit-1ÜÅÜí·¾¯Åà\ª¾Á½è·é)

          //s¾lÌÆ«ÍÆÎ·
          if(dp[i][j][k] == -1) continue;

          //iÔÚÌA[eBXgÉÍÌí¹È¢
          //lÍ¦È¢. Kvàà¦È¢j,kÍ»ÌÜÜ
          //«xà¦È¢
          dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);

          //iÔÚÌÊíA[eBXgðÙÁ½Æ«, ÙpàÌvªlimitð´¦È¢Èç
          if(k + e[i] <= limit){
            //iÔÚÌA[eBXgÉÌí¹é
            //lÍêl¦é. KvàÍ, e[i]¦é.
            //«xÍ, dp[i][j][k]©çs[i]¦é.
            dp[i+1][j+1][k+e[i]] = max((int)dp[i+1][j+1][k+e[i]],(int)dp[i][j][k]+s[i]);
          }
        }
      }
    }

    int ans = 0;
    REP(i,x,m+1){ //KvlxÈãmÈºð©é
      rep(j,limit+1){ //j=Kvà
        //dp[m][i][j]ªs¾lÅÈ­Ä, sec[limit-j] às¾lÅÈ¢Æ«
        //limit-jÍ, V[NbgA[eBXgpÌà
        //sec[limit-j]Í, V[NbgA[eBXgÉ¨¢Ä, (limit-j)ÈºÌàðgÁÄ¾çêéÅå«x
        if(dp[m][i][j] != -1 && sec[limit-j] != -1){ //¶¤ÌðÍ ÁÄàÈ­Äàæ©Á½
          ans = max(ans,(int)dp[m][i][j]+sec[limit-j]);
        }
      }
    }

    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0