Abstract

After I post some wrong advice and got a number of downvotes, I came up with this idea to recollect some upvotes. When I heard that Luogu will release their international version with problem statements translated with LLM, I imagined how would these models translate them. Here's an translated example of the problem P7836 in Luogu translated by myself.

「Wdoi-3」Night Sparrows collecting

Background

There's no soldier without weapons. Mistya has to collect ingredients for her dish before she makes them.

However, the Gensokyo is so huge that many different kinds of ingredients scattered on the ground. Due to a limited capacity of Mistya's pack, she can only choose some of them. The night is coming, and she must prepare all the ingredients she needs for her spot at night.

So she went for your help for collecting ingredients.

Statement

Mistya has a packwith a capacity of $$$v$$$ , and there're $$$x$$$ kinds of ingredients. Mistya can't collect ingredients with a full pack.

To collect as many ingredients as possible and save more time, she will pass through $$$n$$$ collection point in order. Each collection point has a number of ingredients to collect.

In detail, for the $$$i$$$ -th collection point, the number of each type of ingredients are $$$C_{i,1},C_{i,2}\cdots C_{i,x}$$$ , when $$$C_{i,j}$$$ represents the number of the ingredient $$$j$$$ at this point. It's guaranteed that all the $$$i$$$ satisfies $$$\sum_{j=1}^xC_{i,j}\le v$$$ .

At each collection point, Mistya will decide to collect ingredients here or not. On her pleasure of collecting new ingredients, if she decides to collect ingredients here, she will collect them all. However, Mistya can drop some ingredients in her pack.

Different ingredients have different versatilities, while some of them are used frequently and others not. That's the reason why Mistya thinks different ingredients have different values, that the $$$i$$$ -th type has a value of $$$A_i$$$ .

For the diversity of her dish, Mistya will collect as many different type of ingredients. She wants to know the maximum sum of values of the ingredient types remains at least one piece in her pack after passing through these $$$n$$$ collection point. Only calculate them once.

Input

The first line contains three integers $$$n,v,x$$$ .

The second line contains $$$x$$$ integers $$$A_i$$$ , represents values of each type.

The following $$$n$$$ lines each contains $$$x$$$ integers represent $$$C_{i,j}$$$ on the $$$i$$$ -th row and the $$$j$$$ -th column.

Output

Output one integer represents the sum of values.

Sample #1

Sample Input #1

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

Sample Output #1

29

Hints

Sample Explanation 1

Collect ingredients at the first and the third collection point. Notice that you should drop a first-type ingredient. Ultimately, the number of the four types of the ingredients are $$${1,1,0,1}$$$ , so the sum of the value is $$$7+11+11=29$$$ . It's easy to see that there's no better solution.

Constraints

All the test data satisfy:

• $$$1\le n\le 10^6$$$

• $$$1\le x\le 18$$$

• $$$1\le v\le 2000$$$

• $$$0\le C_{i,j},\sum C_{i,j}\le v$$$

• $$$0\le A_i\le 1000$$$

• Subtask 4 is the hack task with $$$0$$$ point. It's guaranteed that the data in the subtask 4 satisfy at least one requirement of subtask 2 or subtask 3.