分数: 900 点
问题陈述
Snuke 正在玩游戏 n 卡片种类叫卡 1 通卡 n。 有 m 本游戏中可用的卡包种类;这 i第一个包包含 s_{i,j} 卡副本 j。 每包至少包含一张卡片。
最初,Snuke 有 c_j 卡副本 j (保证他总共至少有一张牌)。
他可以按任意顺序执行任意次数的以下操作:
- 获得卡包:选择 i=1, \dots,或 m 并获取包含在 i第一个包。
- 交换卡:选择 j=1, \dots,或 n,丢弃 2j 卡副本 j,并获得卡副本一份 ((j \text{ mod } n) + 1)。 (他必须至少有 2j 卡副本 j.)
Snuke 希望总共拥有尽可能少的牌。求 Snuke 最终能拥有的最少卡牌数量。
约束
- 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
输入
输入由标准输入按以下格式给出:
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 有 a_1 卡副本 1, a_2 卡副本 2,和 a_3 卡副本 3。 以下操作序列使 Snuke 只剩下一张牌:
- 得到 1-st 卡包,这会导致 (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 最终可以获得一份卡片副本 4 和卡副本一份 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