Description

Given an $n \times n$ matrix. Each cell contains a non-negative integer $A_{i,j}$ ($A_{i,j} \le 10^3$). Starting from $(1, 1)$, you may move only right or down and finally reach $(n, n)$. Every time you arrive at a cell, you take the number in that cell and the cell’s value becomes $0$. Repeat this walk a total of $K$ times. Find the maximum possible sum of the values collected over the $K$ walks.

Input Format

The first line contains two integers $n, K$ ($1 \le n \le 50$, $0 \le K \le 10$).

The next $n$ lines each contain $n$ integers, denoting the value of each cell in the matrix.

Output Format

Output a single integer, the maximum sum.

3 1
1 2 3
0 2 1
1 4 2

11

Hint

The value in each cell does not exceed $1000$.

Translated by ChatGPT 5