Representing an Image by a Binary Tree

Assignment

A raster picture P made of black and white pixels may be represented by its dimensions and a binary tree created according to the following rules:

If the pixels of P are all of the same color (white or black) then its tree representation consists of the root only and the root contains information about the pixels' color.
Let W (W ≥ 2) be the width of P, let X (1 ≤ X < W) be an integer. Let P₁ be the rectangular part of P which consists of the first X columns of P. Analogously, let P₂ be the rectangular part of P which consists of the last W−X columns of P. In this case, P may be represented by a tree which root contains the value of X and also an attribute specifying vertical division. Furthermore, the left subtree of the root is a tree representation of P₁ and the right subtree of the root is a tree representation of P₂.
Let H (H ≥ 2) be the height of P, let Y (1 ≤ Y < H) be an integer. Let P₁ be the rectangular part of P which consists of the first Y rows of P. Analogously, let P₂ be the rectangular part of P which consists of the last H−Y rows of P. In this case, P may be represented by a tree which root contains the value of Y and also an attribute specifying horizontal division. Furthermore, the left subtree of the root is a tree representation of P₁ and the right subtree of the root is a tree representation of P₂.

The tree representation of a picture may be constructed in various ways and the task is to optimize the tree. The optimization criterion is either the number of nodes or the tree depth. The examples of optimal trees are depicted in Image 1.

Image 1. Examples of raster pictures and the trees which represent the pictures. The divison directions (vertical or horizontal) are depicted by red vertical and horizontal segments both in the pictures and in the tree nodes. The tree nodes contain also the value specifying the position of the corresponding division. The color of the leaves reflect the (unique) color of the corresponding picture area. The upper leftmost pixel of the picture is in the first row and the first column. All depicted trees are optimal in sense of minimal number of nodes and in sense of minimal depth.

The task

A raster picture consisting of black and white pixels is given. Find its optimal tree representation in sense of minimal number of nodes and in sense of minimal depth. Note that these criteria are independent, the tree with minimum depth does not necessarily contain the minimum number of nodes and vice versa. Evaluate each criterion separately.

Input

The first line contains two positive integers M and N separated by space and representing (in this order) the number of rows (height) and the number of colums (width) of the input raster picture. Next, there are M input lines. The lines represent, from top to bottom, particular rows of pixes in the picture. Each row contains N symbols 0/1 separated by spaces. The symbols represent, from left to right, the pixels in the picture, 0 represents white color, 1 represents black color.
The values of M and N do not exceed 50.

Output

The output contains two text lines. The first line contains the value equal to the minimum possible number of nodes in a tree which represents the input picture. The second line contains the value equal to the minimum possible depth of a tree which represents the input picture.

Examples

Example 1

Input

2 2
1 0
1 1

Output

5
2

The data and the solution of Example 1 are depicted in Image 1a).

Example 2

Input

Output

7
3

The data and the solution of Example 2 are depicted in Image 1b).

Example 3

Input

5 6
0 0 1 1 1 1
0 0 1 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
0 1 1 1 0 0

Output

13
3

The data and the solution of Example 3 are depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Link to public data set