knapsack3d

#define FN "knapsack3d"

#include<cstdio>
#include<cctype>
#include<iostream>
#include<fstream>
#include<functional>
#include<utility>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#include<complex>
#include<cstring>
#include<string>
#include<cassert>
#include<iomanip>


using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> vi;
typedef pair<int,int> pii;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(n) (n).begin(), (n).end()
#define EPS 1e-9
#define INF 1e9
#define forn(i, n) for(int i = 0; i < (n); ++i)
#define forab(i, a, b) for(int i = a; (i) < (b); ++(i))
#define forba(i, b, a) for(int i = b-1; i >= (a); --i)
#define forit(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define fornr(i,n) for(int i=(n)-1;i>=0;--i)


vector <int> price, weight, c;

int dp[510][510];

int main(){
#ifdef FN
    freopen(FN".in", "r", stdin);
    freopen(FN".out", "w", stdout);
#endif
    int n, P, W;
    scanf("%d%d%d", &n, &P, &W);
    price.resize(n), weight.resize(n), c.resize(n);
    forn(i, n){
        scanf("%d%d%d", &price[i], &weight[i], &c[i]);
    }
    forn(i, n){
        printf("W = %d, P = %d, C = %d\n", weight[i], price[i], c[i]);
    }
    dp[0][0] = 0;
    forab(i, 1, W+1){
        forab(j, 1, P+1){
            dp[i][j] = dp[i-1][j-1];
            forn(k, n){
                if(weight[k]<=i && price[k]<=j){
                    dp[i][j] = max(dp[i][j], dp[i-weight[k]][j-price[k]]+c[k]);
                }
            }
        }
    }
    forn(i, W+1){
        forn(j, P+1){
            printf("%d ", dp[i][j]);
        }   puts("");
    }
    printf("%d\n", dp[W][P]);
    return 0;
}