#include<bits/stdc++.h> using namespace std; const int N=105; int w[N][N],f[N][N],maxn=0; int n,m; int main(){ while(1){ cin>>n>>m; if(n==0&&m==0)return 0; for(int i=0;i<=m;i++)f[0][i]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)cin>>w[i][j]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=0;k<=m;k++){ if(k>=j)f[i][k]=max(f[i][k],max(f[i-1][k],f[i-1][k-j]+w[i][j])); else f[i][k]=max(f[i-1][k],f[i][k]); maxn=max(f[i][k],maxn); } } } cout<<maxn<<endl; } return 0; }