Description

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).

Input Format

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 Format

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

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

Hint

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