← 返回题目列表

AtCoder · arc112_f

F. 西德勒

中文机器翻译题面 查看原题

分数: 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