#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]
int 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(dp[i+1][j+1][k+e[i]],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,dp[m][i][j]+sec[limit-j]);
        }
      }
    }

    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0