Hide

Problem F
The Components Game

/problems/componentsgame/file/statement/en/img-0001.png

Narwhy the Narwhal likes playing games on his waterproof phone. Recently, he downloaded a new game from the OceanStore. It involves a rectangular grid made of white and black squares. After going through the tutorial, he learned that by touching any column it turns that column completely black. The larger the number of contiguous regions of the same color there are on the board, the higher his score is!

\includegraphics[width=0.5\textwidth ]{narwhy2.png}

Rigorously, these regions are defined as maximal sections of neighboring squares of the same color, where two squares are considered neighbors if they share an edge. After playing the game for a while, Narwhy noticed that between two boards with the same number of total regions, the one with more white regions gets a higher score. Given a state of the board, how can Narwhy get the highest score possible by touching a single column?

Input

Input consists of a single data set. This data set consists of two or more lines of input. The first line contains two decimal integers $N$ and $M$, ($1 \le N, M \le 1\, 000$), which represent the number of rows and the number of columns respectively. Each of the next $N$ lines contains a string of $M$ characters where each character is either a 0 (for a white square) or a 1 (for a black square).

Output

Output two space separated decimal integers which are the number of white regions and the number of black regions corresponding to the highest score that can be obtained by touching exactly one column.

Sample Input 1 Sample Output 1
1 1
0
0 1
Sample Input 2 Sample Output 2
3 3
000
010
110
2 1

Please log in to submit a solution to this problem

Log in