题目背景 那一瞬间，一道白光闪过，从此大地上再也没有了丝毫的响动 那是一个黑暗的晚上。 新纪元59β年，23:13:56，这个悲惨的时刻。 所有人都开始自相残杀，亲人、朋友，都是敌人。 终有人类逃出了这片黑暗的天地，试图挽救这悲惨的未来。 但是腐化生物的能力完全超出了人类的控制范围。 勇者号的主控台与舰桥，人类最后与腐化生物抗衡的希望。 很可惜，α计划失败了，腐化生物即将入侵主控台。人类的最后英雄试图反抗。 这一切都是徒劳。 不！还有最后的希望！毁灭号的等离子充能炮！ 如果不能得到，就将他彻底毁掉。 新纪元596α，下起了倾盆大雨，哭诉着勇者号自豪去死的英雄。 题目描述 水宝宝驾驶着毁灭号接近了勇者号舰桥。 他要使用毁灭号的等离子炮摧毁勇者号主控台。 但是操控等离子炮的程序出了点问题。等离子炮有n个操作信号，第i个操作信号的强度为b[i]。总体强度为各操作信号的强度之和。 由于有些信号太弱了了 (强度0)，水宝宝想把它们删除。但是水宝宝自己不会删除信号，所以他找来了同船的队友帮忙。 有 m位队友，第ii 位队友只会删除编号在 L[i] 和 R[i]之间的信号，且每删除一个信号，花费 C[i]格能量。飞船一共有 k格能量，问他在请队友删除完信号后，总体强度最大是多少。 注:本系列题不按难度排序哦

输入描述:

输入格式：第一行包含三个正整数 n,k,m第二行包含 n个正整数 b1,b2,⋯,bn，表示各信号的强度。接下来 m 行，每行三个正整数Li,Ri,Ci，表示一个队友的属性。

输出描述:

输出格式：输出一行一个整数，表示最大的信号强度

备注:

对于 100% 的数据，1≤n,m≤10^5;1≤k≤500;1≤C[i]≤500;1≤L[i]≤R[i]≤n;-10^9≤b[i]≤10^9新纪596α 12:00:14水宝宝用沾满汗水的双手拉动了操纵杆，将等离子炮对准了勇者号主控台。“再见。勇士们。”水宝宝向勇者号发送了它能接收的最后一条信息。水宝宝用微颤的手摁下了Enter。一声巨响后，世界重归宁静。英雄们倒在了炮火里，没有痛苦。整个世界只剩毁灭号引擎的轰鸣。如果失去了勇者号，我们只能孤注一掷。人类最后的希望，R8IO核弹。北半球的天空，从此只有黑夜。