SONGSHOP Tester

#include<bits/stdc++.h>

using namespace std;

const int MX = 1009;

int n , albums , budget;

vector < pair < int , int > > v[MX];

int albumcost[MX] , dp[MX][MX];

int main(){

    scanf("%d %d %d",&n,&albums,&budget);

    for(int j = 1 ; j <= n ; j++){
        int a , b , c;
        scanf("%d %d %d",&a,&b,&c);
        v[a].push_back({b , c});
    }

    for(int j = 1 ; j <= albums ; j++){
        scanf("%d",&albumcost[j]);
    }

    int song = 0 , ans = 0;

    for(int cur = 1 ; cur <= albums ; cur++){
        int allval = 0;
        for(auto pp : v[cur]){
            ++song;
            allval += pp.second;
            int songcost = pp.first , songval = pp.second;
            for(int spent = budget ; spent >= 0 ; spent--){
                dp[song][spent] = dp[song - 1][spent];
                if(songcost <= spent)
                    dp[song][spent] = max(dp[song][spent] , dp[song - 1][spent - songcost] + songval);
            }
        }
        int prevalbum = song - v[cur].size();
        for(int spent = budget ; spent >= albumcost[cur] ; spent--){
            dp[song][spent] = max(dp[song][spent] , dp[prevalbum][spent - albumcost[cur]] + allval);
        }


    }

    for(int j = 0 ; j < MX ; j++) for(int i = 0 ; i < MX ; i++) ans = max(ans , dp[j][i]);

    cout<<ans<<endl;



}