Tiny Types

A little hero is a $1$ year old prodigy and he just learned about numbers and programming. While he was doing some programming, he saw that numbers can be represented using various data types and he started thinking at a game:

Given $n$ integers and $k$ data types, we want to be able to store the various values using a single variable (after all, our hero is just 1) which can change its datatype if we pay a certain cost. The initialization of the variable is free, however, so we can start with whichever data type we want.

Now the little hero wants to compute the minimum cost of changing the data types so that he's able to represent the various integers he will have to use while processing the input without any kind of overflow.

We can use the data type $i$ in order to store integers from $0$ to $2^i - 1$. There are no negative integers in the input.

However, he can't use too big data types either, so in order to avoid doing that, there is also a penalty for using data types bigger than the minimal size we need to use for a certain number.

For example, if he needs to represent $5$, the smallest data type necessary for storing $5$ is data type $3$, so if he uses data type $5$, the penalty we have is equal to $penalty_2$, since we used a data type two tiers higher than what we needed $5$ - $3$ = $2$.

Input data

The first line of the input contains $n$, the number of integers the little hero needs to represent and $k$, the number of data types.

The next line contains the $n$ integers the hero needs to use, which are represented using the array $v$.

The next $k$ lines contain $k$ integers each, representing the cost of changing the data type from type $i$ to type $j$.

The next line contains $k$ integers, representing the penalty array. It is guaranteed that the penalty array is non-decreasing.

Output data

The output file contains a single integer, representing the minimum cost of processing the data types given the rules described in the statement.

Constraints and clarifications

• $1 \leq n \leq 10^5$
• $1 \leq k \leq 30$
• $0 \leq v_i < 2^k$
• $0 \leq cost_{ij} \leq 100$. It is guaranteed that $cost_{ii} = 0$ for all values $i$.
• $0 \leq penalty_i \leq 100$

Example 1

stdin

5 3
4 2 6 3 1
0 3 2
3 0 1
4 2 0
1 4 7

stdout

4