Migrated from Lutece 2887 驱逐摆摆人3

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大大超人是卷王。 大大超人讨厌摆烂的废物。 大大超人决定驱逐那些摆烂的摆摆人。

由于大大超人太强了，大大超人的领域可以看做一个 $n\times m$ 的矩阵，其中矩阵每个 $1\times 1$ 的区域都有一个摆摆人。 每个摆摆人都要么在摆要么在卷，大大超人讨厌摆烂的摆摆人，所以他决定做一些操作使得摆烂的摆摆人最少。 具体的大大超人每次可以选择一行或一列的摆摆人，然后 $push$ 他们，这样会使得所有摆烂的摆摆人卷起来，但是同时已经在卷的摆摆人会由于压力太大而摆烂。 现在大大超人想知道他能通过不断操作能得到的最少的摆烂的摆摆人的数量是多少。 大大超人当然知道问题的答案，但是为了不让你摆掉，他将问题丢给了你。

Input

第一行读入两个空格隔开的整数 $n,m$。 接下来 $n$ 行每行一个长度为 $m$ 的 $01$ 串描述矩阵中摆摆人的状态。 $0$ 表示摆摆人在卷，$1$ 表示摆摆人在摆烂。

Output

输出一个整数表示最少的摆烂的摆摆人的数量。

Samples

3 3
100
010
001

2

3 9
010100100
101011011
101011101

2

Constraints

$1\le n\le 20$。 $1\le m\le 10^5$。

Note

样例 $1$ 解释： 可以依次对第 $1$ 行，第 $2$ 列，第 $3$ 列操作，得到矩阵为： 000 001 010 可以证明这样摆烂的摆摆人数量最少，为 $2$ 。

Resources

2022 UESTC ICPC Training for Math and Geometry