008 - コイン集め2(Coin Collecting 2)
時間制限 2 秒 / メモリ制限 1024 MB / 得点 100 / x 0 /
問題
机の上に，縦 H 行，横 W 列の長方形状にコインが並べられている． 最初，上から i 行目 ( 1≦i≦H)，左から j 列目 ( 1≦j≦W) のコインは， $S i,j$ = # のとき表面， $S i,j$ = . のとき裏面が見えている状態である． 葵と凛は，これらのコインを用いてゲームを行うことにした．ゲームは以下のような流れで行われる． 葵がどれか 1 つの行を選び，その行のコインをすべてひっくり返す． 凛がどれか 1 つの列を選び，その列のコインをすべてひっくり返す． 葵が，表面が見えるコインをすべて獲得する．また凛が，裏面が見えるコインをすべて獲得する． 葵と凛はそれぞれ，できるだけ多くのコインを獲得したい． ゲーム開始時のコインの状態が与えられたとき， 両者が最善を尽くした場合にそれぞれが獲得できるコインの枚数を求めるプログラムを作成せよ．
入力
入力は以下の形式で標準入力から与えられる。
H W
$S_{1,1}$$S_{1,2}$⋯$S_{1,W}$
$S_{2,1}$$S_{2,2}$⋯$S_{2,W}$
⋮
$S_{H,1}$$S_{H,2}$⋯$S_{H,W}$
出力
葵と凛の得点をこの順に空白区切りで出力せよ．
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- H≧1．
- W≧1．
- H×W≦500000．
-
$S
i,j$は # . のいずれかである (1≦i≦H,1≦j≦W)．
- H,W は整数である．
入出力例
入力例1
1 1 #
出力例1
1 0
この入力例は小課題 1,2,3,5,6,7 の制約を満たす．
入力例2
5 5 ##### ####. ###.. ##... #....
出力例2
13 12
この入力例は小課題 5,6,7 の制約を満たす．
入力例3
1 40 ..........##########..........##########
出力例3
19 21
この入力例は小課題 2,5,6,7 の制約を満たす．
入力例4
7 1 # # # # # # #
出力例4
1 6
この入力例は小課題 3,5,6,7 の制約を満たす．
入力例5
11 14
出力例5
11 14
この入力例は小課題 5,6,7 の制約を満たす．
入力例6
10 40 ........................................ ..######.....####.....#####.....####.... .....#......#....#......#......#........ .....#......#....#......#......#........ .....#......#....#......#......#........ .....#......#....#......#......#..####.. ..#..#......#....#......#......#....#... ..#..#......#....#......#......#....#... ...##........####.....#####.....####.... ........................................
出力例6
104 296
この入力例は小課題 5,6,7 の制約を満たす．