题目描述
Benq驾驶着毁灭号接近了勇者号舰。
他要使用等离子充能炮摧毁勇者号主控台。
但是等离子炮出了点问题。有n台等离子炮，第i个等离子炮的攻击力为b[i]。总攻击力为各个等离子炮的攻击力之和。
由于有些等离子炮出现了奇怪的现象 (攻击力 < 0)，Benq想把它们拆除。但是Benq自己不会拆除，所以他找来了同船的队友帮忙。
有m位队友，第i位队友只会拆除编号在 L[i] 和 R[i]之间的等离子炮，且每删除一个等离子炮，都要花费 C[i]格能量。飞船一共有 k格能量，问他在请队友拆除完等离子炮后，总体攻击力最大值是多少。
1≤ n, m ≤ 10^5 ;
1 ≤ k ≤ 500 ;
1 ≤ C[i] ≤ 500 ;
1 ≤ L[i] ≤ R[i] ≤ n;
-10^9 ≤ b[i] ≤ 10^9。
输入
第一行包含三个正整数 n, m, k；
第二行包含 n个正整数 b1, b2, ⋯ , bn，表示各等离子炮的攻击力；
接下来m行，每行三个正整数Li, Ri, Ci，表示一个队友的属性。
5 5 10
10 -2 -5 7 -10
1 1 5
2 4 10
4 4 12
3 4 10
1 5 15
提示
样例解释：花费10的代价拆除a[3], 答案即为10 + 7 - 10 - 2 = 5