#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

A bear is learning karate! It is practicing the karate chop on *H* planks of length *W* units and height 1 unit, aligned nicely to form a grid of *W***H* square units. We shall call each square unit of the grid a cell. The bear feels bored, and hence decides to play a strange game while practicing karate. Firstly, it takes a red marker and writes a positive integer on every cell of the grid. Then it scribbles *N* **non-zero** integers ≥ -1 on its trusty notebook: *E*_{1}, *E*_{2}, ..., *E _{N}*. Finally it places 1 rock to the right of each plank.

The bear starts with score 0. It has *N* turns. In each turn, it does the following in order:

- The bear chooses a row of planks that has
**exactly**1 rock to the right of it. This being the*i*^{th}turn, it either removes that rock when*E*= -1, or places_{i}*E*extra rocks there otherwise._{i} - The bear decides to practice its math! For every currently available plank of length
*x*units, we shall call it**choppable**if it is possible to chop it into 2 planks of length*a*units and*b*units, such that*a*,*b*are positive integers and*a*+*b*=*x*.

For each**choppable**plank, the bear sums up the red numbers on that plank. The bear then sees how many rocks there are to the right of the planks on that row. Say there are*r*rocks and the sum of numbers is*h*. It then adds*r***h***h*to its score in this game. - The bear then chops every
**choppable**plank in the grid into 2 planks of positive integer lengths in any way it wants.

The bear has played this tedious game once and does not wish to play it again. However, it is wondering, how should it play the game such that it obtains the minimum score?

## Input

The first line contains 3 integers*W*,

*H*,

*N*(1 ≤

*W*≤ 50, 1 ≤

*N*≤

*H*≤ 14). The next

*H*lines each has

*W*integers. The

*j*

^{th}integer of the

*i*

^{th}of these lines is the integer

*A*

_{i,j}(1 ≤

*A*

_{i,j}≤ 50) that the bear writes on the cell on row

*i*, column

*j*(rows and columns are numbered starting from 1). The following line then contains

*N*integers that it writes on its notebook. More specifically, the

*i*

^{th}of these integers

*E*(-1 ≤

_{i}*E*≤ 50,

_{i}*E*≠ 0) tells us the number of extra rocks it would place at the row it chooses in the

_{i}*i*

^{th}turn. If

*E*= -1, then it takes away the rock.

_{i}## Output

The output should consist of 1 line: The minimum score the bear can obtain if it plays the game optimally. The answer is guaranteed to fit in a 32-bit signed integer.## Sample Input 1

3 4 2 2 3 2 1 2 4 5 3 3 2 5 7 -1 2

## Sample Output 1

307

## Explanation for Sample Output 1

The bear first writes the integers on the grid and places the rocks to the right of each row as in the diagram above.

In turn 1, it chooses to take away the rock from the last row. The bear then calculate its new score *S* as follows:

*S* = 1*(2+3+2)^{2} + 1*(1+2+4)^{2} + 1*(5+3+3)^{2} + 0*(2+5+7)^{2} = 219

Then it chops the planks as in the figure above.

In turn 2, it chooses to add 2 rocks to the second row, then calculates its new score *S* as follows:

*S* = 219 + 1*(3+2)^{2} + 3*(1+2)^{2} + 1*(3+3)^{2} + 0*(5+7)^{2} = 307

Then it chops the planks again.

Since *N* = 2, the bear ends the game with a score of 307.

## Sample Input 2

2 2 2 2 8 10 2 1 3

## Sample Output 2

344

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 20 | 1s | 16MB | Average |

2 | 0 | 2 | 1s | 16MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o bearchops -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512