P7836 "Wdoi-3" Night Sparrow Collecting

Even the best cook cannot make a meal without ingredients. Before cooking, Mystia must go around collecting ingredients. However, Gensokyo is simply too large, and all kinds of ingredients are scattered everywhere. Mystia's backpack is very limited, so when collecting, she has to think about what to keep and what to give up. Mystia also has very limited time, because she must prepare all ingredients before setting up her stall at night. So she asks you for help, hoping that you, who are good at calculation, can help her collect ingredients.

Mystia has a backpack with capacity $v$, and there are $x$ types of ingredients. Once the backpack is full, Mystia cannot collect any more ingredients. To collect as many ingredients as possible while also saving time, she will pass through $n$ collection points **in order**. Each collection point provides some amount of ingredients that can be collected. Specifically, for the $i$-th collection point, the counts of each ingredient type are $C_{i,1},C_{i,2}\cdots C_{i,x}$, where $C_{i,j}$ means how many of the $j$-th ingredient type are at this point. It is guaranteed that for all $i$, we have $\displaystyle C_{i,1}+C_{i,2}+\cdots+C_{i,x}=\sum_{j=1}^{x}C_{i,j} \leq v$. At each collection point, Mystia will decide whether to start collecting. Because she really enjoys the pleasure of getting new ingredients, once she starts collecting, she will collect **all** ingredients at this point. Therefore, if her backpack does not have enough remaining capacity to hold all the ingredients here, she **cannot** collect them. Even so, Mystia may choose to discard some ingredients in her backpack before collecting. Different ingredients have different usefulness in cooking: some are used often, while others appear in only a few dishes. Therefore, each ingredient has a different value in Mystia's mind, and the value of the $i$-th type is $A_i$. For the diversity of dishes, Mystia wants to collect as many different types of ingredients as possible. So she wants to know: after passing through these $n$ collection points, what is the maximum possible sum of values of the ingredient types for which she has at least $1$ item in her backpack (that is, if there are multiple items of the same type, it is counted only once).

The first line contains three integers $n,v,x$. The second line contains $x$ integers, representing the value of each ingredient type. The next $n$ lines each contain $x$ integers, where the $j$-th integer on the $i$-th line is $C_{i,j}$.

Output one integer in one line, representing the sum of values.

#### Sample 1 Explanation Collect ingredients at the first and third collection points. Note that before collecting at the third collection point, discard one unit of the first ingredient type. In the end, the counts of the four ingredients are $\{1,1,0,1\}$, so the obtained value sum is $7+11+11=29$. It can be proven that there is no better plan. --- #### Constraints and Notes $$ \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} $$ For $100\%$ of the testdata: $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$, and $0 \le A_i \le 1000$. Subtask 4 is an unscored Hack testdata, guaranteed to satisfy the limits of Subtask 2 or Subtask 3. Special thanks to chenxinyang2006 for the huge contribution to the solution of this problem. Translated by ChatGPT 5