Description
经历过三次消消乐游戏，PIPI早已成为消消乐大神，这次POPO给他带来了一个极具挑战的消消乐游戏。
给定一个有n个元素的集合，PIPI的积分为集合元素之和。PIPI有m次机会，第i次机会可以使[Li,Ri]区间的一个元素变为0，但是其会消耗Ci个游戏币，只要游戏币足够，PIPI可以一直重复使用某次机会的效果。
假设PIPI一开始有k个游戏币，请问他的积分最大是多少？
Input
第一行输入三个正整数n,m,k，其中n,m<=10^5，k<=100。
第二行n个整数ai(-10^9<=ai<=10^9)，表示集合1到n号元素的值。
接下来m行，每行三个数L,R,C，其中：1<=L<=R<=n，1<=C<=100。