← 返回题目列表

AtCoder · abc396_g

G. 翻转行或列

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

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

  1. 操作 Y 与 y=1
  2. 操作 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