MISOLOVKE

문제

There are mice in Mirko's basement! As soon as he realised, he filled his basement with mousetraps. 

His basement can be modelled by an N×N grid. There are a number of mousetraps in each cell and this number is known for each cell. There is at least one mousetrap in every cell. 

Improbably, Slavko also just discovered mice in his basement! However, Slavko has no mousetraps so he came to borrow some from Mirko. Because Mirko already laid out his mousetraps in his basement they needed to figure out what to do. 

They decided to remove some mousetraps from Mirko's basement. More precisely, in each row they will remove all mousetraps from exactly K consecutive cells. After doing this the mice must not be able to cross from the left to the right side of the basement, or from top to bottom. Mice move in the four cardinal directions (up, down, left and right) and can pass only through cells with no mousetraps in them. 

Calculate the largest number of mousetraps that can be removed from Mirko's basement. 

입력

The first line contains two integers N and K (2 ≤ N ≤ 250, 1 ≤ K ≤ N/2), the dimension of the basement and the number of consecutive squares to be removed from each row. 

출력

Output the largest number of mousetraps that can be removed. 

 

4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1

36

3 1
2 2 4
4 1 5
2 3 5

13

6 3
1 2 3 4 5 3
1 6 4 5 1 2
7 3 8 2 1 1
2 1 6 7 3 4
3 1 4 4 4 4
5 6 7 1 1 1

89