Problem Statement

Snuke is playing a game using $n$ kinds of cards called Card $1$ through Card $n$. There are $m$ kinds of card packs available in this game; the $i$-th pack contains $s_{i,j}$ copies of Card $j$. Every pack contains at least one card.

Initially, Snuke has $c_j$ copies of Card $j$ (it is guaranteed that he has at least one card in total).

He can do the following operations any number of times in any order:

• Get a card pack: Choose $i=1$, $\dots$, or $m$ and get all cards contained in the $i$-th pack.
• Exchange cards: Choose $j=1$, $\dots$, or $n$, discard $2j$ copies of Card $j$, and get one copy of Card $((j \text{ mod } n) + 1)$. (He must have at least $2j$ copies of Card $j$.)

Snuke wants to have as few cards as possible in total. Find the minimum number of cards that Snuke can end up with.

Constraints

• $2 \le n \le 16$
• $1 \le m \le 50$
• $0 \le s_{i,j}, c_j \lt 2j$
• $c_1+\dots +c_n>0$
• $s_{i,1}+\dots +s_{i,n}>0$

Input

Input is given from Standard Input in the following format:

n m
c_1 \dots c_n
s_{1,1} \dots s_{1,n}
\vdots
s_{m,1} \dots s_{m,n}

Output

Print the minimum number of cards that Snuke can end up with.