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: E1, E2, ..., EN. 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 ith turn, it either removes that rock when Ei = -1, or places Ei extra rocks there otherwise.
- 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?
The first line contains 3 integers W
(1 ≤ W
≤ 50, 1 ≤ N
≤ 14). The next H
lines each has W
integers. The jth
integer of the ith
of these lines is the integer Ai,j
(1 ≤ Ai,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 ith
of these integers Ei
(-1 ≤ Ei
≤ 50, Ei
≠ 0) tells us the number of extra rocks it would place at the row it chooses in the ith
turn. If Ei
= -1, then it takes away the rock.
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
Sample Output 1
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
Sample Output 2