题目描述

すぬけ君正在玩一个使用 $1$ 到 $n$ 号卡牌共 $n$ 种卡牌的游戏。这个游戏中有 $m$ 种卡包，第 $i$ 种卡包中包含卡牌 $j$ 的数量为 $s_{i,j}$。每个卡包中至少有 $1$ 张卡牌。

最开始，すぬけ君拥有卡牌 $j$ 的数量为 $c_j$（保证他总共至少有 $1$ 张卡牌）。

すぬけ君可以按照任意顺序、任意次数进行以下操作：

• 获得一个卡包：选择 $i=1,\dots,m$ 中的一个卡包，获得该卡包中包含的所有卡牌。
• 交换卡牌：选择 $j=1,\dots,n$ 中的一个卡牌，弃掉 $2j$ 张卡牌 $j$，获得 $1$ 张卡牌 $((j\ \text{mod}\ n)+1)$。（必须拥有至少 $2j$ 张卡牌 $j$ 才能进行此操作。）

すぬけ君希望使自己持有的卡牌总数尽可能少。请你求出他能够达到的卡牌总数的最小值。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出すぬけ君能够达到的卡牌总数的最小值。

样例 1

输入

3 1
0 3 5
0 1 0

输出

1

样例 2

输入

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

输出

2

样例 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

输出

9

说明/提示

限制条件

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

样例解释 1

用 $(a_1, a_2, a_3)$ 表示分别持有 $a_1$ 张卡牌 $1$、$a_2$ 张卡牌 $2$、$a_3$ 张卡牌 $3$。可以按如下方式操作，将卡牌总数变为 $1$ 张：

• 获得第 $1$ 种卡包后，状态为 $(0,4,5)$。
• 选择 $j=2$ 进行卡牌交换，状态变为 $(0,0,6)$。
• 选择 $j=3$ 进行卡牌交换，状态变为 $(1,0,0)$。

无法将卡牌总数变为 $0$，因此 $1$ 是最小值。

样例解释 2

先获得第 $2$ 种卡包两次，再获得第 $1$ 种卡包，然后多次进行卡牌交换，可以使得只持有 $1$ 张卡牌 $4$ 和 $1$ 张卡牌 $5$。

由 ChatGPT 4.1 翻译