题目描述

すぬけくんはカード $1$ からカード $n$ の $n$ 種類のカードを使うゲームで遊んでいます。 このゲームには、カードパックが $m$ 種類存在し、$i$ 種類目のカードパックにはカード $j$ が $s_{i,j}$ 枚含まれています。 どのカードパックにもカードが $1$ 枚以上含まれています。

最初、すぬけくんはカード $j$ を $c_j$ 枚持っています（合計で $1$ 枚以上のカードを持っていることが保証されます）。

すぬけくんは、次の操作を好きな順番で好きな回数行うことができます。

• カードパックをもらう：$i=1,\dots,m$ のうちひとつを選ぶ。$i$ 種類目のパックに含まれるカードをすべて手に入れる。
• カードを交換する：$j=1,\dots,n$ のうちひとつを選ぶ。カード $j$ を $2j$ 枚捨てて、カード $((j\ \text{\ mod\ }\ n)\ +\ 1)$ を $1$ 枚手に入れる。（カード $j$ を $2j$ 枚以上持っていなければならない。）

すぬけくんは持っているカードの総数をできるだけ少なくしたいです。すぬけくんが達成できるカードの総数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すぬけくんが達成できるカードの総数の最小値を出力せよ。

题目大意

现在有 $n$ 种牌和 $m$ 种牌包，第 $i$ 种牌包有 $s_{i,j}$ 张第 $j$ 种牌。

初始时你有 $c_j$ 张第 $j$ 种牌。你可以以任意顺序执行下列操作之一任意多次：

• 选择 $1\leq i\leq m$ ，获得第 $i$ 种牌包所有牌。每种牌包都有无穷个。
• 选择 $1\leq j\leq n$ ，要求有 $\ge 2j$ 个第 $j$ 类牌。扔掉 $2j$ 个第 $j$ 类牌，并获得 $1$ 张第 $j\bmod n+1$ 类牌。

最小化最终剩余牌数。

3 1
0 3 5
0 1 0

1

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

2

12 10
0 2 4 4 1 5 6 8 0 9 18 19
1 2 4 3 4 0 6 10 9 18 5 7
0 3 0 1 1 4 11 13 9 19 9 10
1 2 4 1 5 8 1 6 15 0 11 1
0 2 0 6 9 3 13 14 16 9 14 14
1 3 2 5 6 1 9 7 1 7 6 22
0 0 4 5 2 3 8 3 13 14 17 4
0 3 3 4 0 7 0 9 14 2 17 14
0 2 4 1 3 3 3 14 17 6 15 13
0 0 1 0 1 0 4 5 9 4 17 17
1 2 1 3 5 7 0 13 7 6 1 0

9

提示

制約

• $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$

Sample Explanation 1

カード $1$ を $a_1$ 枚、カード $2$ を $a_2$ 枚、カード $3$ を $a_3$ 枚持っていることを $(a_1,\ a_2,\ a_3)$ と書くことにします。 以下のように操作をすると、カードの総数を $1$ 枚にすることができます。 - $1$ 種類目のカードパックをもらう。$(0,4,5)$ となる。 - $j=2$ を選んでカードを交換する。$(0,0,6)$ となる。 - $j=3$ を選んでカードを交換する。$(1,0,0)$ となる。 カードの総数を $0$ 枚にすることはできないため、これが最小です。

Sample Explanation 2

$2$ 種類目のカードパックを $2$ パックもらったあと、$1$ 種類目のカードパックをもらい、その後何度かカードを交換すると、 カード $4$ とカード $5$ を $1$ 枚ずつ持っている状態が作れます。