P2045 Grid Number Picking - Enhanced

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.

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 a single integer, the maximum sum.

The value in each cell does not exceed $1000$. Translated by ChatGPT 5