AT_arc112_f.[ARC112F] Die Siedler

すぬけ君正在玩一个使用 $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}$

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

限制条件

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