You are given NxM matrix .Each cell of matrix has some numbers . You can choose some rectangles of any size so that sum of numbers in all rectangles is maximum . But there are condition of choosing the rectangles .

The first and last rectangles must touch first row & column and last row & column of given matrix respectively . All the other rectangles except first rectangle must be at right and bottom side of the previous rectangle and no rectangle should overlap .

Find the maximum sum we can get .