"友好对待"组长

待定MiB 1000 ms

题目描述

$YYC$ 是某组的组长，他有$m$个组员。

因为$YYC$上课玩游戏被老师扣分, 所以组员们很愤怒，要殴打他。因为时间紧迫只能殴打他$n$秒。
组员们想让最后殴打的点数尽量的大，而$YYC$暗自记了一个累加伤害变量$Q$,一开始$Q:=0$
同时，由于殴打$YYC$会消耗体力，因此还需要记录每个组员的体力值，第$i$个组员初始体力值为$y_i$。

接下来是对殴打过程的具体描述：

对于第$i$秒：

• 对于第$j$个组员，它有两种选择：
  1.殴打$YYC$,造成$a_{i,j}$点伤害，并且使自己的体力值减去$b_{i,j}$，同时,$Q:=Q+a_{i,j}$ $($执行此操作的前提是原先体力值$\geq b_{i,j})$。
  2. 不殴打$YYC$,这会使自己的体力增加$c_{i,j}$。

• 如果$Q\geq X$,$YYC$会反击。他会令所有人的体力值变为$0$，同时，$Q:=0$。

因为小组成员殴打$YYC$时间紧迫,他们想让你来算出最多能殴打多少点，注意，此处并非$YYC$的$Q$，而是所有殴打的点数的总和。

输入格式

第一行三个整数$n,m$和$X$，表示殴打总时间,组员数和$YYC$的忍受限度。 接下来一行$m$个整数，第$i$个数表示$y_i$。 接下来$nm$行，每行三个整数,第$(i-1)m+j(1\leq i\leq n 且1\leq j\leq m )$行的数分别为$a_{i,j},b_{i,j},c_{i,j}$。

输出格式

一行一个整数，表示殴打的点数的总和的最大值。

数据范围与提示

(待定，因为具体做法还没想出来)