Problem Statement

There are $N$ skills numbered $1$ to $N$ and $M$ achievements numbered $1$ to $M$.

Each skill has a positive integer level, and the initial level of every skill is $1$.

You can pay a cost of $C_i$ yen to increase the level of skill $i$ by $1$. You can do this as many times as you want.

Achievement $i$ is achieved when the following condition is satisfied for every $j=1,\ldots,N$, for which you will receive a reward of $A_i$ yen.

• Condition: The level of skill $j$ is at least $L_{i,j}$.

Find the maximum possible total reward obtained minus the total cost required when appropriately choosing how to raise the skill levels.

Constraints

• $1 \leq N,M \leq 50$
• $1 \leq L_{i,j} \leq 5$
• $1 \leq A_i,C_i \leq 10^6$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
C_1 \ldots C_N
A_1 \ldots A_M
L_{1,1} \ldots L_{1,N}
\vdots
L_{M,1} \ldots L_{M,N}

Output

Print the answer as an integer.