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:

1. Each tile covers two positions of the table that are next to each other (adjacent) either in a row or in a column.
2. The tiles can touch but not overlap.
3. 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