Codeforces 663E FWT

E. Binary Table

time limit per test

6 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a table consisting of n rows and m columns. Each cell of the table contains either 0 or 1. In one move, you are allowed to pick any row or any column and invert all values, that is, replace 0 by 1 and vice versa.

What is the minimum number of cells with value 1 you can get after applying some number of operations?

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 20, 1 ≤ m ≤ 100 000) — the number of rows and the number of columns, respectively.

Then n lines follows with the descriptions of the rows. Each line has length m and contains only digits '0' and '1'.

Output

Output a single integer — the minimum possible number of ones you can get after applying some sequence of operations.

Example

Input

Output

题意: 

给定一个n*m的01矩阵(n<=20),可以选择反翻转一些行或者列。问可以获得的最少的1的个数。

思路:

由于n很小,可以将m列看成m个n bit整数。对于行操作,可以看成异或上一个数(下面假设这个数是z),对于列操作,可以看成翻转某一个数。最后让1的数目最少。假设sta[x]为x在上述的m个数中出现的次数,res[x]为x中的1和x取反后1的个数的最小值。令ans[z] 为所有数异或x后的答案1的最小的数目,那么$ans[z] = \sum sta[x] * G[x\oplus z] $ 根据异或的性质,可以变成 $ans[z \oplus x] = \sum sta[x] * G[z] $,这样预处理出sta和G数组,用FWT进行异或卷积,再求出ans数组的最小值即可。