Mystia’s Backpack Collection Optimization

Mystia has a backpack with capacity \(v\) and there are \(x\) different types of ingredients with given values \(A_1, A_2, \dots, A_x\). She will visit \(n\) collection points sequentially. At the \(i\)th collection point, there are \(x\) numbers \(C_{i,1}, C_{i,2}, \dots, C_{i,x}\) where \(C_{i,j}\) is the number of ingredient of type \(j\) available. It is guaranteed that

[ C_{i,1} + C_{i,2} + \cdots + C_{i,x} \le v \quad \text{for all } i=1,2,\dots,n. ]

When she arrives at a collection point, Mystia must decide whether to collect the ingredients at that point. If she chooses to collect, she must take all the ingredients found at that point. However, before collecting, she is allowed to discard any ingredients currently in her backpack. If after discarding, her backpack cannot hold all the ingredients from that point (i.e. the total number of items in the backpack plus the new items would exceed \(v\)), then she cannot collect at that point.

Define the set of ingredient types offered at the \(i\)th point as

[ P_i = { j \mid C_{i,j} > 0 }. ]

Because Mystia cares about the diversity in her cooking, she only counts an ingredient type once regardless of how many units she has; its contribution to the final score is its given value \(A_j\) if at least one unit of type \(j\) is in the backpack.

When collecting at a point, since she must take all items offered there, the final set \(S\) of ingredients in her backpack (where \(|S| \le v\)) will be the union of some of the collected points. However, note that if she collects at a point, then the offered set \(P_i\) must be a subset of her final set \(S\) (because she cannot discard part of the collected batch). Moreover, for every ingredient type \(j\) in her final set \(S\), there must be at least one collection point \(i\) such that \(j \in P_i\) and \(P_i \subseteq S\).

Your task is to determine the maximum total value \(\sum_{j \in S} A_j\) that Mystia can achieve in her backpack after visiting all collection points.

inputFormat

The first line contains three integers: \(v\), \(x\), and \(n\).

The second line contains \(x\) integers: \(A_1, A_2, \dots, A_x\) representing the values of the ingredient types.

Then \(n\) lines follow. The \(i\)th of these lines contains \(x\) non-negative integers: \(C_{i,1}, C_{i,2}, \dots, C_{i,x}\). It is guaranteed that for each \(i\), \[ \sum_{j=1}^{x} C_{i,j} \le v. \]

outputFormat

Output a single integer: the maximum total value sum of distinct ingredient types that can be present in Mystia's backpack after she finishes visiting all collection points.

sample

3 3 2
1 2 3
1 0 0
0 1 1

6