CF1804D.Accommodation

Annie is an amateur photographer. She likes to take pictures of giant residential buildings at night. She just took a picture of a huge rectangular building that can be seen as a table of $n \times m$ windows. That means that the building has $n$ floors and each floor has exactly $m$ windows. Each window is either dark or bright, meaning there is light turned on in the room behind it.

Annies knows that each apartment in this building is either one-bedroom or two-bedroom. Each one-bedroom apartment has exactly one window representing it on the picture, and each two-bedroom apartment has exactly two consecutive windows on the same floor. Moreover, the value of $m$ is guaranteed to be divisible by $4$ and it is known that each floor has exactly $\frac{m}{4}$ two-bedroom apartments and exactly $\frac{m}{2}$ one-bedroom apartments. The actual layout of apartments is unknown and can be different for each floor.

Annie considers an apartment to be occupied if at least one of its windows is bright. She now wonders, what are the minimum and maximum possible number of occupied apartments if judged by the given picture?

Formally, for each of the floors, she comes up with some particular apartments layout with exactly $\frac{m}{4}$ two-bedroom apartments (two consecutive windows) and $\frac{m}{2}$ one-bedroom apartments (single window). She then counts the total number of apartments that have at least one bright window. What is the minimum and maximum possible number she can get?

安妮是一名业余摄影师，她喜欢在夜间拍摄巨大的住宅楼。她刚刚拍摄了一栋巨大的矩形建筑，该建筑可视为一个 $n \times m$ 的窗户网格：即该建筑共有 $n$ 层，每层恰好有 $m$ 扇窗户。每扇窗户要么是暗的，要么是亮的，表示其后房间内的灯是否开启。

安妮知道，这座建筑中的每个公寓要么是一居室，要么是两居室。每个一居室公寓在照片中恰好对应一扇窗户；每个两居室公寓则在同一层上恰好对应两扇相邻的窗户。此外，题目保证 $m$ 可被 $4$ 整除，且已知每层恰好有 $\frac{m}{4}$ 个两居室公寓和 $\frac{m}{2}$ 个一居室公寓。公寓的实际布局未知，且每层的布局可能不同。

安妮将一个公寓视为“被占用的”，当且仅当其至少一扇对应的窗户是亮的。现在她想知道：依据给定的照片，被占用公寓数的最小值与最大值分别是多少？

形式化地说：对每一层，她均可设计一种特定的公寓布局，其中恰好包含 $\frac{m}{4}$ 个两居室公寓（即 $\frac{m}{4}$ 对相邻窗户）和 $\frac{m}{2}$ 个一居室公寓（即 $\frac{m}{2}$ 个单独窗户）。随后，她统计所有至少有一扇亮窗的公寓总数。那么，她所能得到的该总数的最小值与最大值分别是多少？

The first line of the input contains two positive integers $n$ and $m$ ($1 \leq n \cdot m \leq 5 \cdot 10^5$) — the number of floors in the building and the number of windows per floor, respectively. It is guaranteed that $m$ is divisible by $4$.

Then follow $n$ lines containing $m$ characters each. The $j$-th character of the $i$-th line is "0" if the $j$-th window on the $i$-th floor is dark, and is "1" if this window is bright.

输入的第一行包含两个正整数 $n$ 和 $m$（$1 \leq n \cdot m \leq 5 \cdot 10^5$），分别表示建筑物的楼层数和每层的窗户数量。保证 $m$ 能被 $4$ 整除。

接下来是 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符为 "0" 表示第 $i$ 层的第 $j$ 扇窗户是暗的，为 "1" 表示该窗户是亮的。

Print two integers, the minimum possible number of occupied apartments and the maximum possible number of occupied apartments, assuming each floor can have an individual layout of $\frac{m}{4}$ two-bedroom and $\frac{m}{2}$ one-bedroom apartments.

输出两个整数：在每层楼可以独立布局 $\frac{m}{4}$ 套两居室公寓和 $\frac{m}{2}$ 套一居室公寓的前提下，可能的最少入住房间数和最多入住房间数。

In the first example, each floor consists of one two-bedroom apartment and two one-bedroom apartments.

The following apartment layout achieves the minimum possible number of occupied apartments equal to $7$.

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

The following apartment layout achieves the maximum possible number of occupied apartments equal to $10$.

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

在第一个例子中，每层楼包含一套两居室公寓和两套一居室公寓。

以下公寓布局实现了最少可能的已入住公寓数量，即 $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|