题目描述

小理是个大厨，早上起来他开始一天的工作。

他所在的餐厅每天早上都会买好 $n$ 件食材（每种食材的数量可以视为无限），小理从到达餐厅开始就连续工作 $T$ 时间。

每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。

第 $i$ 道菜肴有三个属性 $a_i,b_i,c_i$ ,$a_i$ 是该菜肴的美味值，$b_i$ 是该菜肴所选食材不新鲜的速率，如果在第 $t$ 时刻完成第 $i$ 道菜则美味值为：$a_i-t*b_i$ ，完成这道菜需要 $c_i$ 的时间。小理希望在这 $T$ 时间内能做出菜肴使得总美味值最大，所以小理求助于你。

输入格式

第1行输入三个整数 $n$ ， $m$ ， $T$ ,分别代表食材种类，菜肴种类和工作时间。

第 $2$ 行输入 $n$ 个整数 $b_i$ ，代表第 $i$ 个食材不新鲜的速率。

接下来的 $m$ 行，每行输入三个整数 $j$ ，$a_i$ ，$c_i$ ​，分别代表第 $i$ 道菜肴需要的食材编号，菜肴的美味值，完成时间。

美味值必须通过完整做出菜肴得到，数据保证在规定时间内至少能完整做出 $1$ 道菜肴。

输出格式

输出一行，一个整数，表示最大总美味值。

样例输入输出

样例输入#1

1 1 74
2
1 502 47

样例输出#1

408

样例输入#2

2 2 10
2 1
1 100 8
2 50 3

样例输出#2

84

数据范围

对于 $100%$ 的数据，保证 $0<n,m≤50,0<j≤n$ ,其他值均 $<10^6$ 。

提示说明

最大总美味值可能为负。