K取方格数

题目描述:

在N*N的矩形网格中，每个格子里都写着一个整数。可以从左上角到右下角安排K条路线，每一步只能往下或往右，沿途经过的格子中的整数会被取走。若多条路线重复经过一个格子，只有第一次经过该格子时能取到数，即每一格子的数只被取一次。求能取得的整数的和最大是多少。

输入格式:

第一行包含N 和 K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) 

接下来N行描述N*N的矩阵，矩阵中的每个数都小于1000的整数。

输出格式:

一个数，表示最后能取到的最大的和值。

样例输入:

3 2
1 2 3
0 2 1
1 4 2

样例输出:

15

提示:

N<=50, K<=10。

时间限制: 1000ms
空间限制: 256MB

---