Image Grid Compactness

Security personnel wish the cells displaying images on a screen to be as compact as possible. The compactness is measured by the area of the smallest axis‐aligned rectangle that contains all the displayed images. There are four buttons available: left, right, up, and down. When a button is pressed, every image in the grid moves one cell in that direction if it is not already at the corresponding boundary of the grid.

For example, consider an initial layout whose compactness is \(12\). After pressing the “right” button once and the “up” button once, the compactness becomes \(4\).

Given a grid of size n \(\times\) m containing some images (denoted by '1'), determine the minimum possible compactness that can be achieved by pressing these buttons in some sequence and also compute the minimum number of button presses required to achieve that compactness.

The compactness is defined as \(A = (\max\{r\} - \min\{r\} + 1) \times (\max\{c\} - \min\{c\} + 1)\), where \(r\) and \(c\) represent the row and column indices (1-indexed) of the images in the grid after performing the moves.

inputFormat

The first line contains two integers n and m (the number of rows and columns of the grid).

Then follow n lines, each containing a string of m characters. Each character is either '0' (empty cell) or '1' (cell containing an image).

outputFormat

Output two integers separated by a space: the minimum compactness (i.e. the area of the smallest rectangle covering all images) and the minimum number of button presses required to achieve that compactness.

sample

3 3
010
000
010

2 1