Mouse Traps

Time limit1sMemory limit128 MB

Summary

Given an N x N grid of trap counts, choose K consecutive cells per row to remove so no path exists left-to-right or top-to-bottom, maximizing removed traps.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Greedy
Solved: No attempts yet

Problem

Sanggeun found mice in his basement. Because he strongly dislikes mice, he installed many mouse traps there.

The basement is represented as an N x N grid. Each cell stores the number of mouse traps installed in that cell, and every cell contains at least one trap.

Jeongin also found mice in his basement. Since no traps are available for him to buy, he wants to borrow some traps from Sanggeun.

After discussing it, they decide that Sanggeun will remove some traps from his basement and give them to Jeongin. More precisely, for each row of the grid, Sanggeun chooses K consecutive cells, removes all traps in those selected cells, and gives those traps to Jeongin.

After the traps are removed, a mouse must not be able to travel through Sanggeun's basement from the left wall to the right wall, nor from the top wall to the bottom wall. A mouse can move in the four cardinal directions and can pass only through cells with no remaining traps.

Find the maximum number of traps that can be removed while satisfying these conditions.

Input

The first line contains N and K. N is the size of the basement, and K is the number of consecutive cells that must be selected in each row.

2 <= N <= 250, 1 <= K <= N/2

Output

Print the maximum number of traps that can be removed from Sanggeun's basement.

Examples3

Example 1
Input
```
4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1
```
Expected output
```
36
```
Example 2
Input
```
3 1
2 2 4
4 1 5
2 3 5
```
Expected output
```
13
```

Example 3

Input

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

Expected output