Problem G. Garden of mystery

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Eccentric millionaire Vasiliy Vorotkin-Tretij has a garden.

The garden is a rectangular area extending W meters from east to west and H meters from north to east. Each 1 × 1 meter square is either covered with walkable grass (represented by '.' character, ASCII 46) or by impenetrable bushes (represented by '#' character, ASCII 35).

A set of grass squares is a secluded area if:

  1. there is a path between every pair of squares in the set, such that
  2. each square in the path belongs to the set and has a common side with the previous square in the path;
  3. there are no more grass squares in the rest of the garden which have a common side with any square in the set.

Mystery level of garden is the number of secluded areas within it.

Vasiliy is quite proud of his garden's mystery level, and has decided to improve it. For this, he wants to build an additional wall of bushes from north to south across all the garden (i.e. replace all grass squares in a single column by bush squares).

Your program must find a location for a north-south wall which maximizes mystery level.

In the second sample, original garden has mystery level 1. Replacing all grass squares in the 4th column by bushes will create five secluded areas, shown by digits in a picture.

111#2#
#1##2#
3#4#2#
3#####
333#55

Input file format

First line of input file contains integers W H. Following H lines contain W characters each — garden representation.

Output file format

Output file must contain two integers: maximum possible mystery level and number of column to be replaced by a wall (columns are numbered left to right from 1 to W).

If there are several optimal solutions, output one with the minimum column number.

Constraints

1 ≤ W, H ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 1
.....
2 2
2
6 5
.....#
#.##.#
.#...#
.##.##
......
5 4
3
1 1
#
0 1

0.076s 0.008s 13