Treasure island
Problem
Monk wants to divide an island which is in the form of N * M matrix into pieces of 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.
First line contains 2 integers N and M.
Then N lines follow each containing M integers.
Print the minimum cost required.
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
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).
