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 \)
First we split the matrix with cost 8 and get 2 matrices as (2,2) and (1,3).
Now we can split (2,2) with cost 4 into (2) and (2).
Now we can split (1,3) with cost 4 into (1) and (3).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor