SONGSHOP Author

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5010;
const int MAXPRICE = 5010;

int n, m, totalPrice;
vector<pair<long long, long long> > albums[MAXN];

long long dp[MAXN][MAXPRICE], albumPrice[MAXN], albumValue[MAXN];

int main() {
    cin >> n >> m >> totalPrice;
    for (int i = 0; i < n; i++) {
        int x, y, val;
        cin >> x >> y >> val;
        albums[x].push_back({y, val});
        albumValue[x] += val;
    }
    for (int i = 1; i <= m; i++)
        cin >> albumPrice[i];
    int idx = 0;
    for (int i = 1; i <= m; i++) {
        for (auto song: albums[i]) {
            idx++;
            for (int price = 0; price <= totalPrice; price++) {
                dp[idx][price] = max(dp[idx - 1][price], (price >= song.first) ? dp[idx - 1][price - song.first] + song.second : 0);
            }
        }
        idx++;
        for (int price = 0; price <= totalPrice; price++) {
            dp[idx][price] = max(dp[idx - 1][price], (price >= albumPrice[i]) ? dp[idx - (int)albums[i].size() - 1][price - albumPrice[i]] + albumValue[i] : 0);
        }
    }
    cout << dp[idx][totalPrice] << endl;
    return 0;
}