输入描述:

第1行输入三个整数  ,分别代表食材种类，菜肴种类和工作时间。
第2行输入  个整数 ，代表第  个食材不新鲜的速率。
接下来的m行，每行输入三个整数，分别代表第  道菜肴需要的食材编号，菜肴的美味值，完成时间。
数据保证：，其他值均，美味值必须通过完整做出菜肴得到，数据保证在规定时间内至少能完整做出1道菜肴。

输出描述:

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

备注:

最大总美味值可能为负。