310245: CF1804D. Accommodation

D. Accommodationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

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.

ExamplesInput

5 4
0100
1100
0110
1010
1011

Output

7 10

Input

1 8
01011100

Output

3 4

Note

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|

题目大意：
安妮是一个业余摄影师，她喜欢在夜晚拍摄巨大的住宅楼。她刚刚拍摄了一栋巨大的矩形建筑的照片，这栋建筑可以看作是一个有$n \times m$窗户的表格。这意味着建筑有$n$层，每层有$m$个窗户。每个窗户要么是暗的，要么是亮的，表示房间里是否有灯光亮着。

安妮知道这栋大楼的每个公寓要么是一室公寓，要么是两室公寓。每个一室公寓在照片上恰好有一个窗户代表它，每个两室公寓在同一层恰好有两个连续的窗户。此外，$m$的值保证能被4整除，并且知道每层恰好有$\frac{m}{4}$个两室公寓和$\frac{m}{2}$个一室公寓。实际公寓的布局是未知的，并且每层都可能不同。

安妮认为，如果一个公寓至少有一个窗户是亮的，那么这个公寓就被认为是被占用的。她现在想知道，根据给定的照片，被占用公寓的最小和最大可能数量是多少？

输入输出数据格式：
输入：
第一行包含两个正整数$n$和$m$（$1 \leq n \cdot m \leq 5 \times 10^5$）——建筑物的层数和每层的窗户数。保证$m$能被4整除。
然后是$n$行，每行包含$m$个字符。如果第$i$层第$j$个窗户是暗的，则第$i$行的第$j$个字符是"0"，如果是亮的，则是"1"。

输出：
打印两个整数，分别是被占用公寓的最小可能数量和最大可能数量，假设每层可以有个体布局的两室公寓$\frac{m}{4}$和一室公寓$\frac{m}{2}$。题目大意： 安妮是一个业余摄影师，她喜欢在夜晚拍摄巨大的住宅楼。她刚刚拍摄了一栋巨大的矩形建筑的照片，这栋建筑可以看作是一个有$n \times m$窗户的表格。这意味着建筑有$n$层，每层有$m$个窗户。每个窗户要么是暗的，要么是亮的，表示房间里是否有灯光亮着。 安妮知道这栋大楼的每个公寓要么是一室公寓，要么是两室公寓。每个一室公寓在照片上恰好有一个窗户代表它，每个两室公寓在同一层恰好有两个连续的窗户。此外，$m$的值保证能被4整除，并且知道每层恰好有$\frac{m}{4}$个两室公寓和$\frac{m}{2}$个一室公寓。实际公寓的布局是未知的，并且每层都可能不同。 安妮认为，如果一个公寓至少有一个窗户是亮的，那么这个公寓就被认为是被占用的。她现在想知道，根据给定的照片，被占用公寓的最小和最大可能数量是多少？ 输入输出数据格式： 输入： 第一行包含两个正整数$n$和$m$（$1 \leq n \cdot m \leq 5 \times 10^5$）——建筑物的层数和每层的窗户数。保证$m$能被4整除。 然后是$n$行，每行包含$m$个字符。如果第$i$层第$j$个窗户是暗的，则第$i$行的第$j$个字符是"0"，如果是亮的，则是"1"。 输出： 打印两个整数，分别是被占用公寓的最小可能数量和最大可能数量，假设每层可以有个体布局的两室公寓$\frac{m}{4}$和一室公寓$\frac{m}{2}$。