Coin Collecting 2

Interview

Time limit2sMemory limit1024 MB

Summary

Aoi flips one row and Rin flips one column, each trying to collect more coins. Find both players' counts under optimal play.

Level: Medium4 of 10
Topics: Math, Brute force, Implementation
Solved: No attempts yet

Problem

On the desk, coins are arranged in a rectangle with $H$ rows and $W$ columns. Initially, the coin in row $i$ from the top ( $1 \leq i \leq H$ ) and column $j$ from the left ( $1 \leq j \leq W$ ) shows its front side if $S_{i,j}=$ #, and its back side if $S_{i,j}=$ ..

Aoi and Rin play a game with these coins. The game proceeds as follows.

Aoi chooses one row and flips all coins in that row.
Rin chooses one column and flips all coins in that column.
Aoi collects all coins showing front sides. Rin collects all coins showing back sides.

Each of them wants to collect as many coins as possible.

Given the initial state of the coins, write a program that finds how many coins each player collects when both play optimally.

Input

The input is given in the following format.

H W
S1,1 S1,2 … S1,W
S2,1 S2,2 … S2,W
︙
SH,1 SH,2 … SH,W

Output

Print Aoi's score and Rin's score in this order, separated by a space.

Constraints

$H \geq 1$ .
$W \geq 1$ .
$H \times W \leq 500\,000$ .
Each $S_{i,j}$ is either # or . ( $1 \leq i \leq H$ , $1 \leq j \leq W$ ).
$H$ and $W$ are integers.

Examples5

Example 1
Input
```
1 1
#
```
Expected output
```
1 0
```

Example 2

Input

5 5
#####
####.
###..
##...
#....

Expected output

13 12

Example 3

Input

1 40
..........##########..........##########

Expected output

19 21

Example 4
Input
```
7 1
#
#
#
#
#
#
#
```
Expected output
```
1 6
```

Example 5

Input

5 5
.###.
...##
..##.
.##..
##...

Expected output

11 14