move（Hard Version）
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题与《E. move (Easy Version)》共享部分题目背景，这一部分文本我们将使用特殊的格式加以标注。
〖引用开始〗
\hspace{15pt}给定一个长为 n 宽为 m 的矩阵 a，其中矩阵中每个格子都有一个权值，第 i 行第 j 列的权值记为 a_{i,j}，现在你能够执行以下两种操作之一：
\hspace{23pt}\bullet\,选择矩阵中某个位置 \left ( i,j \right ) \left ( 1\leqq i\leqq n;\, 1\leqq j<m \right )，令 u:=\left(a_{i,j}\operatorname{or} a_{i,(j+1)}\right)、v:=\left(a_{i,j}\operatorname{and} a_{i,(j+1)}\right)，使得 a_{i,j}:=u、a_{i,(j+1)}:=v。
\hspace{23pt}\bullet\,选择矩阵中某个位置 \left ( i,j \right ) \left ( 1\leqq i<n;\, 1\leqq j\leqq m \right )，令 u:=\left(a_{i,j}\operatorname{or} a_{(i+1),j}\right)、v:=\left(a_{i,j}\operatorname{and} a_{(i+1),j}\right)，使得 a_{i,j}:=u、a_{(i+1),j}:=v。
〖引用结束〗
\hspace{15pt}你需要构造一个从列下标 1,2,\dots,m 中选取 k \left( 0\leqq k\leqq m \right) 个数构成的集合 \Bbb{A}，记剩余 m-k 个数构成的集合为 \Bbb{B}，使得能通过若干次上述操作（可以为零次），将矩阵 a 变成满足以下条件的新矩阵：
\hspace{23pt}\bullet\,对于任意的 j\in \Bbb{A}、i\in[1,n]，满足 a_{i,j}=1；
\hspace{23pt}\bullet\,对于任意的 j\in \Bbb{B}、i\in[1,n]，满足 a_{i,j}=0；
\hspace{15pt}如果有多个这样的集合 \Bbb{A} 满足要求，找出字典序最大的一个。随后，求解该字典序最大化的集合 \Bbb{A} 所需要的将矩阵 a 变成满足条件的新矩阵的最少操作次数（不需要输出具体的构造）；如果没有满足要求的集合 \Bbb{A}，则输出 -1。

【名词解释】
\hspace{15pt}\operatorname{or}：指位运算中的按位或（Bitwise OR），对两个整数的二进制表示按位进行或运算。
\hspace{15pt}\operatorname{and}：指位运算中的按位与（Bitwise AND），对两个整数的二进制表示按位进行与运算。
\hspace{15pt}集合的字典序比较：将集合元素升序排列后，从小到大逐个比较两个集合的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素大的集合字典序也大。如果一直比较到其中一个集合结束，则长度较长的集合字典序更大。

输入描述:

\hspace{15pt}第一行输入两个整数 n,m \left ( 1\leqq n\leqq 120;\,1\leqq m \leqq 500\right )，分别表示矩阵的长和宽。
\hspace{15pt}此后 n 行，第 i 行输入 m 个整数 a_{i,1}, a_{i,2}, \ldots, a_{i,m} \left ( 0\leqq a_{i,j}\leqq 1 \right )，表示矩阵中第 i 行的权值。

输出描述:

\hspace{15pt}如果有满足条件的字典序最大化的集合 \Bbb{A}，则输出该集合所需要的将矩阵 a 变成满足条件的新矩阵的最少操作次数；否则输出 -1。
示例1

输入

复制 
4 5
1 0 0 0 1
0 1 0 0 1
1 0 1 0 0
0 0 0 1 1

输出

复制 
10

说明

\hspace{15pt}在这个样例中，集合 \Bbb{A}=\{1,3\} 是字典序最大的集合，最终的矩阵为：\begin{bmatrix}<br />1 & 0 & 1 & 0 & 0 \\<br />1 & 0 & 1 & 0 & 0 \\<br />1 & 0 & 1 & 0 & 0 \\<br />1 & 0 & 1 & 0 & 0 \\<br />\end{bmatrix}。
示例2

输入

复制 
2 3
0 0 0
0 0 0

输出

复制 
0

说明

\hspace{15pt}在这个样例中，不需要任何操作就能满足要求。
示例3

输入

复制 
3 3
1 0 1
1 1 1
1 1 0

输出

复制 
-1

说明

\hspace{15pt}在这个样例中，找不到任何的集合 \Bbb{A} 满足要求。
示例4

输入

复制 
10 10
0 0 0 0 0 1 1 1 0 0
1 0 0 0 0 1 1 1 1 1
1 1 0 1 1 0 1 0 0 0
1 1 1 0 0 0 1 0 0 0
0 1 0 1 0 1 0 1 0 1
0 1 0 1 1 0 1 1 1 0
0 0 1 0 1 0 1 0 0 1
0 1 1 0 1 0 1 1 1 0
0 1 0 0 0 0 1 1 1 0
0 1 1 1 0 1 1 0 1 1

输出

复制 
109