公寓布局

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

Annie 是一名业余摄影师。她喜欢在夜晚拍摄巨大的居民楼。她刚刚拍摄了一张矩形建筑的照片，这栋建筑可以看作一个 $n\times m$ 的窗口矩阵：共有 $n$ 层，每层恰好有 $m$ 个窗口。每个窗口要么是黑暗的，要么是明亮的，表示其后房间的灯是否亮着。

这栋楼里的每套公寓要么是一居室，要么是两居室。一居室公寓在照片上恰好对应一个窗口；两居室公寓恰好对应同一层上两个相邻的窗口。每层恰好有 $\frac m4$ 套两居室公寓和 $\frac m2$ 套一居室公寓。每层的实际布局未知，并且不同楼层的布局可以不同。

如果一套公寓至少有一个明亮的窗口，就认为这套公寓有人居住。对每一层，你可以独立选择一种合法布局。求所有楼层中有人居住的公寓总数的最小值和最大值。

输入格式

第一行包含两个正整数 $n,m$，分别表示楼层数和每层的窗口数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的 01 字符串。第 $i$ 行的第 $j$ 个字符为 0 表示第 $i$ 层第 $j$ 个窗口是黑暗的，为 1 表示该窗口是明亮的。

输出格式

输出两个整数，分别表示可能的有人居住公寓总数的最小值和最大值。

样例输入 1

5 4
0100
1100
0110
1010
1011

样例输出 1

7 10

样例输入 2

1 8
01011100

样例输出 2

3 4

样例说明

在第一个样例中，每层由一套两居室公寓和两套一居室公寓组成。

下面的布局可以得到最小值 $7$。竖线分隔不同公寓，空格连接同一套两居室公寓的两个窗口。

|0 1|0|0|
|1 1|0|0|
|0|1 1|0|
|1|0 1|0|
|1|0|1 1|

下面的布局可以得到最大值 $10$。

|0 1|0|0|
|1|1 0|0|
|0 1|1|0|
|1|0 1|0|
|1 0|1|1|

数据范围

保证：

• $1\le n\cdot m\le 5\times10^5$；
• $m$ 能被 $4$ 整除。