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