Shooting Practice

The board is an $N \times N$ grid with at least one target. A student practices shooting and has bullets numbered 1 through $K$. The student makes $K$ shots in total, firing bullets 1 through $K$ in order.

For each shot, the student picks one row from 1 to $N$ and fires along it. A bullet starts at the leftmost column (column 1) of that row and travels one cell at a time from left to right. Each bullet has an attack power.

On the initial board, a cell with a target holds a positive integer, and an empty cell holds 0. The value of a target cell is its initial health, which is the current health at the start. When a bullet reaches a target, the target's current health drops by the bullet's attack power. A bullet cannot pass through a target, and it disappears on contact.

When a target's current health reaches 0 or less, the target disappears and the student earns points equal to its initial health. Then, for each empty cell directly above, below, left, or right of the vanished target, a new target is created. The new target's initial health is one quarter of the vanished target's initial health, rounded down. If that value is 0, no new target is created.

At the start, each target's initial health and current health are equal. A target with a value of 10 or more is a bonus target. Bonus targets have no separate initial health. When a bullet hits a bonus target, the bullet and the bonus target both disappear regardless of the bullet's attack power, and the student immediately earns the points written on the bonus target. A bonus target does not create new targets when it disappears. A regular target, one that is not a bonus target, has an initial health from 1 to 9.

Given the initial board, find the maximum score the student can earn with $K$ shots. All $K$ shots can be taken from the same position (the same row). Each bullet's attack power is a natural number from 1 to 100.

For example, take $N=5$ and $K=3$. Assume the bullets' attack powers are 1, 5, and 1 in order. Then there are 5 positions to shoot from. The initial score is 0.

1. The first bullet has attack power 1. Shooting from position 2 hits the bonus target, and the score becomes 10.

2. The second bullet has attack power 5. Shooting from position 2 hits a regular target, and the score becomes 14.

3. The third bullet has attack power 1. Shooting from position 1 hits a regular target, and the score becomes 15.

The shots above give a score of 15, which is the maximum for this example.

The first line contains the board size $N$, a natural number from 2 to 8. The second line contains the number of shots $K$, a natural number from 1 to 5. Lines 3 through $N+2$ give the $N \times N$ board. Values are separated by spaces and are integers from 0 to 30. Line $N+3$ lists the attack powers of bullets 1 through $K$ in order, separated by spaces. Each attack power is a natural number from 1 to 100.

When the $K$ shots are fired, print the maximum score the student can earn on the first line as a natural number.