problem-6-4

Sumeet has an N*N table, where a non-negative integer is written at each position (i,j) of the table.He wants to place J tiles on top of the table that will cover the fields that are too large.
But, there are certain conditions:
Each tile covers two positions of the table that are next to each
    other (adjacent) either in a row or in a column.
The tiles can touch but not overlap.
The sum of all uncovered positions is to be minimized.

It will always be possible to place the J tiles without violating any of the above conditions.

Sumeet wants to determine the minimal sum of visible positions. As you are a great programmer, he asks you to help him out.   

Input format
The first line of input contains two integers N dimension of the table and J, the number of tiles.
Each of the following N lines contains N integers describing the table.

Output format
Output the minimal sum of visible fields after covering the table with tiles.

Constraints

 1 ≤ N ≤ 2000 
 1 ≤ J ≤ 8 
 1 ≤ integer value at each cell  ≤ 1000 

Note : There is no partial score for this problem

SAMPLE INPUT
3 1
2 7 6
9 5 1
4 3 8

SAMPLE OUTPUT
31

Explanation

Cover the cell (2,1) and (2,2) [ 1 - based indexing ]

Source: hackerearth | Difficulty: HARD


Solutions: