记录编号	133955	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2014-10-28 22:26:30	内存使用	0.34 MiB

/*====================================================================================*/
/*==================================by Asm.Def========================================*/
/*====================================================================================*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <ctime>
#include <iterator>
#include <functional>
#include <cstdlib>
using namespace std;
#define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it) 
#define pb push_back
#define REP(i,j,k) for(i = j;i <= k;++i)
#define REPD(i,j,k) for(i = j;i >= k;--i)
typedef long long LL;
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("bus.in","r");
FILE *out = fopen("bus.out","w");
#endif
template <typename T>inline void getint(T &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
}
inline void putLL(const LL &k){
	if(k < 1000000000)fprintf(out, "%d\n", k);
	else{
		int l = k / 1000000000, r = k % 1000000000;
		fprintf(out, "%d%09d\n", l, r);
	}
}
/*===================================WORK============================================*/
#define maxx(a, b) ((a) > (b) ? (a) : (b))
#define minx(a, b) ((a) < (b) ? (a) : (b))
const int maxn = 1000 + 2, maxm = 10000 + 2;
int n, m, k, D[maxn], L_T[maxn] = {0}, off_cnt[maxn] = {0};
int cost[maxn] = {0}, Scnt[maxn] = {0}, seg_r[maxn];

int main(){
	fscanf(in, "%d%d%d", &n, &m, &k);
	LL ans = 0;
	int i, j, T, A, B;
	for(i = 1;i < n;++i)getint(D[i]);
	while(m--){
		getint(T), getint(A), getint(B);
		ans -= T;
		L_T[A] = maxx(L_T[A], T);
		++off_cnt[B];
	}
	for(i = 1;i < n;++i){
		cost[i + 1] = maxx(cost[i], L_T[i]) + D[i];
		Scnt[i + 1] = Scnt[i] + off_cnt[i + 1];
	}
	j = 1;
	for(i = 1;i <= n;++i){
		while(j <= i || (j < n && cost[j] > L_T[j]))++j;
		seg_r[i] = j;
	}
	while(k){
		int maxcnt = 0, iter, mink = k;
		for(i = 1;i <= n;++i)
			if(D[i] && Scnt[seg_r[i]] - Scnt[i] > maxcnt){
				maxcnt = Scnt[seg_r[i]] - Scnt[i];
				iter = i;
			}
		if(!maxcnt)break;
		mink = minx(mink, D[iter]);
		for(i = iter + 1;i < n && cost[i] > L_T[i];++i)
			mink = minx(mink, cost[i] - L_T[i]);
		k -= mink; D[iter] -= mink;
		for(i = iter + 1;i <= seg_r[iter];++i)
			cost[i] = maxx(cost[i-1], L_T[i-1]) + D[i-1];
		j = 1;
		for(j = i = iter;i < seg_r[iter];++i){
			while(j <= i || (j < n && cost[j] > L_T[j]))++j;
			if(j >= seg_r[i])break;
			seg_r[i] = j;
		}
	}
	for(i = 2;i <= n;++i)
		ans += (LL)off_cnt[i] * cost[i];
	putLL(ans);
	//---------------------------------------------------------------------------------
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}
/*===================================================================================*/