C++

#include <cstdio>

#include <cstring>

#include <climits>

#include <algorithm>

using namespace std;

int N,K;

int dt[110][100010];//[n][k]

int dobo_t[110],dobo_m[110];

int ride_t[110],ride_m[110];

const int MIN_ = -1000000 * 100;

int serch(int n,int k){

    if(n==0&&k>=0)

        return 0;

    if(k<0)

        return MIN_;

    if(dt[n][k]!=-1)

        return dt[n][k];

    return dt[n][k]=max(serch(n-1,k-dobo_t[n])+dobo_m[n],serch(n-1,k-ride_t[n])+ride_m[n]);

}

int main()

{

    memset(dt,-1,sizeof(dt));

    scanf("%d %d",&N,&K);

    for(int i=1;i<=N;i++){

        scanf("%d %d %d %d",&dobo_t[i],&dobo_m[i],&ride_t[i],&ride_m[i]);

    }

    printf("%d",serch(N,K));

    return 0;

}