巴西之战，张飞强攻不行，假借醉酒麻痹敌人，引诱张郃放弃坚固的营寨，主动来攻，最终指挥后军偷袭张郃营寨，大败敌军，斩敌两万。

张飞喜欢喝酒是非常出名的，张飞手下有一个非常擅长酿酒的人名叫酒神。

为了酿酒，特地种了一些庄稼，庄稼在区域l_i,r_i会进行一次成熟，酒神就会收集该区域的庄稼，庄稼占用的空间是r_i - l_i+1，每个庄稼都有一个甜美度a_i，他收割的庄稼我们会把它计算出一个甜美度总和，每次收集后，该区域[l,r]庄稼甜美度会增加-100\leq d_i \leq 100;

酒神会用V空间的庄稼进行酿酒，请你帮忙求解一下如何挑选庄稼使得酿的酒甜美度最高，最好喝！

第一行三个数字n,m,V，V表示酿酒最大的庄稼容量;

第二行n个数字，表示庄稼初始的甜美度a_i;

接下来每行3个数字l_i,r_i,d_i，分别表示收割该地区的庄稼，然后收割完后，增加该地区庄稼的甜美度d_i；

达到V空间庄稼酿的酒的最高甜美度

样例说明：

第1次收割，占用2，甜美度3，庄稼的甜美度变成2,3,3,4,5;

第2次收割，占用2，甜美度6，庄稼的甜美度变成2,4,4,4,5;

第3次收割，占用3，甜美度10，庄稼的甜美度变成3,5,5,4,5;

第4次收割，占用2，甜美度9，庄稼的甜美度变成3,5,5,5,6;

数据范围：

40%的数据，n,m\leq 100,V \leq 5000;

100%的数据，n\leq 5\times 10^5,m \leq 4000,V \leq  5\times10^5;