问题描述

Snuke正在玩一款使用n种卡片的游戏，这些卡片从Card1到Cardn编号。在此游戏中有m种卡包可用；第i个卡包包含si,j张Cardj。每个卡包至少包含一张卡片。

初始时，Snuke拥有c_j张Cardj（保证他至少拥有一张卡片）。

他可以按任意次数按任意顺序进行以下操作：

• 获得一个卡包：选择i=1、...、或m，并获得第i个卡包中的所有卡片。
• 交换卡片：选择j=1、...、或n，丢弃2j张Cardj，并获得一张Card ((j mod n) + 1)的副本。（他必须至少拥有2j张Cardj。）

Snuke希望尽可能少地拥有卡片。找出Snuke最终可能拥有的卡片的最小数量。

约束条件

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

输入

输入的格式如下：

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

输出

打印Snuke最终可能拥有的卡片的最小数量。

示例输入1

3 1
0 3 5
0 1 0

示例输出1

1

假设$(a_1, a_2, a_3)$表示Snuke拥有$Card 1$的$a_1$张副本，$Card 2$的$a_2$张副本和$Card 3$的$a_3$张副本。以下操作序列将使Snuke只剩下一张卡片：

• 获得第1个卡包，结果为$(0,4,5)$;
• 交换$j=2$的卡片，结果为$(0,0,6)$;
• 交换$j=3$的卡片，结果为$(1,0,0)$。

不可能最终拥有零张卡片，因此这是可能的最小数量。

示例输入2

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

示例输出2

2

通过获取两种类型的卡包各两个和一种类型的卡包一个，然后进行任意次数的交换操作，Snuke可以最终拥有$Card 4$的一张副本和$Card 5$的一张副本。

示例输入3

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

示例输出3

9