solution

贪心+dp。

做这个题我们需要处理两个问题。第一个是如何确定这些菜的顺序，第二个是确定了菜的顺序之后如何计算答案。

先来确定菜的顺序。仔细观察之后，发现其实这个问题贪心思路和“国王的游戏”一样。如果只考虑两种菜。我们如果让在前，那么选这两种菜的答案就是，否则就是。发现都有，所以我们按照后面那一项排序，也就是，如果大于就让在前，否则让在前。

这样一遍就解决了第一个问题。然后就是第二个问题，用表示前种菜，用了的时间最大的收益。这就是一个简单的01背包了。

因为空间不够，所以要滚动数组或者压掉第一维。

code

/*
* @Author: wxyww
* @Date:   2020-04-27 11:11:24
* @Last Modified time: 2020-04-27 11:37:50
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1000010;
#define int ll
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
struct node {
    ll a,b,c;
}a[N];
bool cmp(const node &A,const node &B) {
    return A.c * B.b < B.c * A.b;
}
ll tmp[N];
ll f[N];
signed main() {
    int n = read(),m = read(),T = read();
    for(int i = 1;i <= n;++i) tmp[i] = read();
    for(int i = 1;i <= m;++i) {
        a[i].b = tmp[read()];a[i].a = read();
        a[i].c = read();
    }

    sort(a + 1,a + m + 1,cmp);

    memset(f,-0x3f,sizeof(f));

    f[0] = 0;
    for(int i = 1;i <= m;++i) {
        for(int j = T;j >= a[i].c;--j) {
            f[j] = max(f[j],f[j - a[i].c] + a[i].a - j * a[i].b);
        }
    }

    ll ans = -1e16;
    for(int i = 1;i <= T;++i)
        ans = max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}