方格取数加强版

题目描述

给出一个n\*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入输出格式

输入格式


第一行两个数n,k(1<=n<=50, 0<=k<=10) 接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式


一个数,为最大和

输入输出样例

输入样例 #1

3 1
1 2 3
0 2 1
1 4 2

输出样例 #1

11

说明

每个格子中的数不超过1000