#5005. Flip coins

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Roger

题目描述

N 行硬币,每行 9 个硬币,排成一个 N * 9 的方阵,有的硬币正面朝上,有的反面朝上。

我们每次可以把一整行或者一整列的所有硬币翻过来,请问怎么翻,使得正面朝上的硬币尽量多。

输入格式

第一行一个数 N 输入一个 N * 9 的方阵

输出格式

一个数,即正面朝上的硬币最多的数目

样例

input

3
111001110
111111110
000001011

output

23

数据范围与提示

1/6 的数据 N \leq 100 ;

5/12 的数据 N \leq 1000 ;

100 % 的数据 N \leq 10000 ;

另: 25 % 的数据翻转次数不超过6次