Accommodation
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 2000
Tags: brute force, dp, greedy, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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$$$.

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

Example input:
5 4
0100
1100
0110
1010
1011

Example output:
7 10

Example input:
1 8
01011100

Example output:
3 4

Editorial:
The number of one-bedroom and two-bedroom apartments is the same for each floor and each floor can have its own independent apartments layout. Thus, we can independently solve the problem for each floor and then just sum the results. Below is given the solution for one floor in $$$O(m)$$$ time.
First, lets introduce some variables.
• $$$B$$$ is the total number of bright windows.
• $$$D$$$ is the total number of dark windows.
• $$$O_0$$$ is the number of one-bedroom apartments that are not occupied ($$$0$$$ bright windows).
• $$$O_1$$$ is the number of one-bedroom apartments that are occupied ($$$1$$$ bright window).
• $$$T_0$$$ is the number of two-bedroom apartments that are not occupied ($$$0$$$ bright windows).
• $$$T_1$$$ is the number of two-bedroom apartments that are occupied and have $$$1$$$ bright window.
• $$$T_2$$$ is the number of two-bedroom apartments that are occupied and have $$$2$$$ bright windows.
• $$$A$$$ is the total number of occupied apartments.
We know that $$$A = O_1 + T_1 + T_2$$$ and $$$B = O_1 + T_1 + 2 \cdot T_2$$$. Thus, $$$A = B - T_2$$$, so in order to minimize the number of occupied apartments we need to maximize $$$T_2$$$ and vice versa.
Maximizing $$$T_2$$$ is easier, you just determine the length of all maximal segments of bright windows, denote these lengths as $$$l_0, l_1, l_2, \ldots, l_x$$$. Then you pack each segment with as many two-bedroom apartments as possible. So, the maximum possible value of $$$T_2 = \min(\sum_{i = 0}^{x} \lfloor \frac{l_i}{2} \rfloor, \frac{m}{4}$$$. Here we must note the importance of having exactly $$$\frac{m}{4}$$$ two-bedroom apartments and exactly $$$\frac{m}{2}$$$ one-bedroom apartments. If the actual number of apartments of each type was given in the input we won't be able to guarantee the value of $$$T_2$$$ defined above. It could be the case that it is not actually possible to place all the remaining apartments and close the gaps between the placement of two-bedroom apartments with two bright windows. However, as we have $$$\frac{m}{2}$$$ one-bedroom apartments we can guarantee that such a placement is always possible.
Now we would like to minimize $$$T_2$$$. Actually, we will do it in exactly the same way as the maximization, but instead of taking maximal segments of bright windows, we will find and use maximal segments that have at least one dark window and do not have two consecutive bright windows. Denote the lengths of such maximal segments as $$$l'_0, l'_1, l'_2, \ldots, l'_y$$$. Then, the minimum possible $$$T_2 = \min(0, \frac{m}{4} - \sum_{i=0}^{y} \lfloor \frac{l'_i}{2} \rfloor)$$$. Again, thanks to $$$\frac{m}{2}$$$ one-bedroom apartments we will be able to fill all the gaps and achieve the desired placement.