P2045 方格取数加强版

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

无

无

每个格子中的数不超过 $1000$。