「Wdoi-3」夜雀 collecting

巧妇难为无米之炊。在制作菜品之前，米斯蒂娅必然要四处收集食材了。 然而幻想乡实在是太大，四处散落着各种各样的食材。米斯蒂娅的背包却非常有限，以至于四处采集时不得不考虑取舍的问题了。米斯蒂娅的时间非常有限，因为她必须要在夜晚摆摊之前准备好所有的食材。 于是她来向你求助，希望精通计算的你帮助她收集食材。

米斯蒂娅有一个容量为 $v$ 的背包，而食材有 $x$ 种。当背包被塞满后，米斯蒂娅就不能够采集更多的食材了。 为了尽可能地收集到更多食材，又要节省更多时间，她会**依次**经过 $n$ 个采集点。每个采集点都会有一定量的食材可供采集。 具体来说，对于第 $i$ 个采集点，每种食材的个数分别为 $C_{i,1},C_{i,2}\cdots C_{i,x}$ ，其中 $C_{i,j}$ 代表该采集点有多少个第 $j$ 种食材。保证对于所有 $i$ ，都有 $\displaystyle C_{i,1}+C_{i,2}+\cdots+C_{i,x}=\sum_{j=1}^{x}C_{i,j} \leq v$ 。 每到一个采集点，米斯蒂娅都会决定是否开始采集食材。因为她非常享受采集新食材带来的愉悦感，一旦开始采集，她会将这个采集点的食材**全部采集完**。因此，如果此时她背包不足以塞下这里所有的食物，她将**不能进行**采集。尽管如此，米斯蒂娅也可以选择在采集前丢弃背包里的一些食材。 不同的食材在烹饪中的泛用性是不同的，一些食材会经常使用，而一些食材则只会出现于少数菜品。因此，每种食材在米斯蒂亚心中有着不同的价值，第 $i$ 种的价值为 $A_i$。 为了菜品的多样性，米斯蒂娅会尽可能采集更多种类的食材。于是她想知道，在经过了这 $n$ 个采集点后，她的背包中至少有 $1$ 个的食材的价值和最大是多少（也就是说，如果一种食材有多个，那么只计算一次）。

第一行三个整数 $n,v,x$。 第二行 $x$ 个整数，表示每种食材的价值。 接下来 $n$ 行，每行 $x$ 个整数，第 $i$ 行的第 $j$ 个整数表示 $C_{i,j}$。

一行一个整数，表示价值和。

5 3 4
7 11 7 11 
1 0 0 1 
2 1 0 0 
1 1 0 0 
1 0 2 0 
1 0 0 2 

29

#### 样例 1 解释 在第一个和第三个采集点收集食材。要注意的是，在采集第三个采集点前，丢弃一个第一种食材。最终，四个食材的数量分别是 $\{1,1,0,1\}$，于是获得的价值和为 $7+11+11=29$。可以证明，没有更优的方案。 --- #### 数据范围及约定 $$ \def{\arraystretch}{2} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm x & \bm n & \textbf{分值}\cr \hline 1 & 1\le x \le 10 & 1\le n\le 2\times 10^3 & 20 \cr\hline 2 & 1\le x \le 14 & 1\le n\le 10^6 & 40 \cr\hline 3 & 1\le x \le 18 & 1\le n\le 1000 & 40 \cr\hline \end{array} $$ 对于 $100\%$ 的数据，有 $1 \le n \le 10^6$，$1 \le x \le 18$，$1 \le v \le 2000$，$0 \le C_{i,j}$，$\sum_{j=1}^x C_{i,j} \le v$，$0 \le A_i \le 1000$。 Subtask 4 为不计分的 Hack 数据， 保证满足 Subtask 2 或 Subtask 3 的限制。 特别感谢 chenxinyang2006 对本题解法的巨大贡献。