分数: 600 点
问题陈述
有一个 H \times W 网格,每个单元格包含 0 or 1。牢房位于 i从顶部开始的第行和 j从左边算起第 1 列包含一个整数 A_{i,j}.
您可以按任意顺序执行以下两项操作任意次数:
- 操作X:选择一个整数 x (1 \leq x \leq H)。对于每个整数 1 \leq y \leq W,替换 A_{x,y} 与 1 - A_{x,y}.
- 运算Y:选择一个整数 y (1 \leq y \leq W)。对于每个整数 1 \leq x \leq H,替换 A_{x,y} 与 1 - A_{x,y}.
找到以下的最小可能值 \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} 处理后。
约束
- 1 \leq H \leq 2\times 10^5
- 1 \leq W \leq 18
- H 和 W 是整数。
- A_{i,1}A_{i,2}\ldots A_{i,W} 是一个长度-W 字符串组成
0和1.
输入
输入由标准输入按以下格式给出:
H W
A_{1,1}A_{1,2}\ldots A_{1,W}
A_{2,1}A_{2,2}\ldots A_{2,W}
\vdots
A_{H,1}A_{H,2}\ldots A_{H,W}
输出
打印答案。
示例输入 1
3 3 100 010 110
示例输出 1
2
通过执行以下操作,网格将发生如下所示的变化,您将得到 \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} = 2.
- 操作 Y 与 y=1
- 操作 X 与 x=2

不可能使 \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} \leq 1,所以答案是 2.
示例输入 2
3 4 1111 1111 1111
示例输出 2
0
示例输入 3
10 5 10000 00111 11000 01000 10110 01110 10101 00100 00100 10001
示例输出 3
13