Monk wants to divide an island which is in the form of N * M matrix into pieces of \(1*1\) matrices.He can do the splitting of the island by making a horizontal cut or a vertical cut. In each case the island gets divided into 2 pieces. There are certain coins in each cell. The cost of split is the sum of all the cells in the island which is to be split.

Monk wants to split the island in minimum cost.Help Monk do so.

\(Input Format\)

First line contains 2 integers N and M.

Then N lines follow each containing M integers.

\(Output Format\)

Print the minimum cost required.

\(Constraints\)

\(1 \le N,M \le 50 \)

\(1 \le coins \le10^5 \)