#P2045. 方格取数加强版

方格取数加强版

题目描述

给出一个 n×nn\times n 的矩阵,每一格有一个非负整数 Ai,jA_{i,j}Ai,j103A_{i,j} \le 10^3),现在从 (1,1)(1,1) 出发,可以往右或者往下走,最后到达 (n,n)(n,n),每达到一格,把该格子的数取出来,该格子的数就变成 00,这样一共走 KK 次,现在要求 KK 次所达到的方格的数的和最大。

输入格式

第一行两个数 n,Kn,K1n501 \le n \le 500K100 \le K \le 10)。

接下来 nn 行,每行 nn 个数,分别表示矩阵的每个格子的数。

输出格式

一个数,为最大和。

3 1
1 2 3
0 2 1
1 4 2
11

提示

每个格子中的数不超过 10001000