3212: 人见人爱的zero
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：4
题目描述
zero最近新学会了一个魔法，他可以将石头变成金币(是不是很神奇，你肯定也想学) 在学会了这个魔法之后，zero瞬间成了有钱人，但可惜的是，zero在学习该魔法的时候没有认真听，导致变出来的金币在第二天没有用完，在第三天就会变回去(当然已经用了的金币是不会变回去的，肯定不能坑人的嘛，zero是一个好孩子的).
zero有m个好朋友，每个朋友会有一段时间和zero待在一起玩，而且每天需要消费一定数量的金币。zero还有n天就要毕业了，在接下来的n天中，每天zero都会通过魔法获得一些金币，同时zero每天需要消费v个金币(保证每天获得的金币至少能够满足zero的消费需求),剩下的金币zero可以留着第二天消费，也可以选择给他的好朋友，当然也包括他喜欢的妹子.但是zero如果决定给别人金币的话，那么就一定会满足他的要求数量，因为zero实在是太好了.当zero给了朋友金币，就会获得1友好度，那么zero在毕业前最多可以获得多少友好度呢。
zero有m个好朋友，每个朋友会有一段时间和zero待在一起玩，而且每天需要消费一定数量的金币。zero还有n天就要毕业了，在接下来的n天中，每天zero都会通过魔法获得一些金币，同时zero每天需要消费v个金币(保证每天获得的金币至少能够满足zero的消费需求),剩下的金币zero可以留着第二天消费，也可以选择给他的好朋友，当然也包括他喜欢的妹子.但是zero如果决定给别人金币的话，那么就一定会满足他的要求数量，因为zero实在是太好了.当zero给了朋友金币，就会获得1友好度，那么zero在毕业前最多可以获得多少友好度呢。
输入
第一行是两个数 n, v(1≤n,v≤400), 表示zero还有n天毕业，每天需要消费v个金币
第二行是n个数，记为a_1,a_2,…,a_n, 分别表示zero每天可以获得的金币的数目，同时满足1≤a_i≤ 400
第三行是一个数m (1≤m≤400) 表示一共有m个朋友，接下来有m行，每一行分别有3个数l,r,c. (1≤l≤r≤n,1≤c≤400)对于该行，表示该朋友在第l天到第r天会和zero待在一起，并且每天需要消费c个金币.
第二行是n个数，记为a_1,a_2,…,a_n, 分别表示zero每天可以获得的金币的数目，同时满足1≤a_i≤ 400
第三行是一个数m (1≤m≤400) 表示一共有m个朋友，接下来有m行，每一行分别有3个数l,r,c. (1≤l≤r≤n,1≤c≤400)对于该行，表示该朋友在第l天到第r天会和zero待在一起，并且每天需要消费c个金币.
输出
输出只有一个数，表示zero可以获得的最多的友好度.
样例输入 复制
4 1
3 2 5 4
3
1 3 2
1 4 1
3 4 2样例输出 复制
7提示
第一天可以获得3个金币，自己消费1个金币，然后给2号朋友1个金币，此时还剩下1个金币，并获得了1友好度
第二天可以获得2个金币，自己消费第一天剩下的1个金币，给2号朋友1个金币，此时还剩下1个金币，并获得了1友好度
第三天可以获得5个金币，自己消费第二天剩下的1个金币，给1号朋友2个金币，给2号朋友1个金币，给3号朋友2个金币，此时还剩下0个金币，获得了3友好度
第四天可以获得4个金币，自己消费1个金币，给2号朋友1个金币，3号朋友2个金币，获得了2友好度。总共获得7友好度
第二天可以获得2个金币，自己消费第一天剩下的1个金币，给2号朋友1个金币，此时还剩下1个金币，并获得了1友好度
第三天可以获得5个金币，自己消费第二天剩下的1个金币，给1号朋友2个金币，给2号朋友1个金币，给3号朋友2个金币，此时还剩下0个金币，获得了3友好度
第四天可以获得4个金币，自己消费1个金币，给2号朋友1个金币，3号朋友2个金币，获得了2友好度。总共获得7友好度