k取方格数
Description
给出一个\(n*n\)的矩阵,每一格有一个非负整数\(A_{ij},(A_{ij} \le 1000)\)现在从\((1,1)\)出发,可以往右或者往下走,最后到达\((n,n)\),每达到一格,把该格子的数取出来,该格子的数就变成\(0\),这样一共走\(K\)次,现在要求\(K\)次所达到的方格的数的和最大。
Input
- 第一行两个数n,k（\(1\le n\le 50, 0\le k\le 10\)）
- 接下来n行,每行n个数,分别表示矩阵的每个格子的数
Output
- 一个数,为最大和
Sample
Input
3 1
1 2 3
0 2 1
1 4 2
Output
11
Hint
\(|A_{i,j}|\le 100\)。1s时限，256mb内存。
