每日一题（美味佳肴）

首先我们发现如果交换两个菜肴做的顺序，sum(ai)是不变的，也就是只剩下两个变量。此时容易想到可以通过代数运算得到做菜顺序。其实贪心思路也挺显然的，肯定是让减少的少的先做，并且同时和做这道菜的时间有关，所以我们此时通过代数运算得到当a.c/a.b < b.c/b.c的时候，先做a是优于先做b的。 然后就是一个标标准准的01背包。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


const int N = 2e6 + 50;
ll n, m, T;
struct node {
    ll a, b, c;
}a[N];
bool cmp(const node &x, const node &y) {
    return x.c * y.b < y.c * x.b;
}
ll p[N], dp[N];
int main()
{
    cin >> n >> m >> T;
    for(int i = 1; i <= n; i ++){
        cin >> p[i];
    }
    for(int i = 1; i <= m; i ++){
        ll q; 
        cin >> q >> a[i].a >> a[i].c;
        a[i].b = p[q];
    }
    memset(dp ,-0x3f, sizeof dp);
    dp[0] = 0;
    sort(a + 1, a + 1 + m, cmp);
    for (int i = 1; i <= m; i ++){
        for (int j = T; j >= a[i].c; j --){
            dp[j] = max(dp[j], dp[j - a[i].c] + a[i].a - j * a[i].b);
        }
    }
    ll res = -1e9;
    for (int i = 1; i <= T; i ++) res = max(res, dp[i]);
    cout << res;
    return 0;
}