#include <bits/stdc++.h>
using namespace std;
int n,k,i,j,a[1010][1010],sum[1010][1010],s,nr,l,li,co,summ[1010][1010],S,lin[1010][1010],c,ma,su;
queue<int>q;
int main()
{
    freopen("ferma2.in","r",stdin);
    freopen("ferma2.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; ++i)
        for(j=1; j<=i; ++j)
        {
            scanf("%d",&a[i][j]);
            S+=a[i][j];
        }
    l=n-k;
    for(i=n; i>=1; --i)
    {
        while(!q.empty())q.pop();
        co=i;
        li=n;
        nr=0;
        s=0;
        while(li>=n-i+1&&co>=1)
        {
            ++nr;
            s+=a[li][co];
            q.push(a[li][co]);
            if(nr==l)
            {
                sum[li][co]=s;
                --nr;
                s-=q.front();
                q.pop();
            }
            --li;
            --co;
        }
    }
    for(j=1; j<=n; ++j)
    {
        while(!q.empty())q.pop();
        s=0;
        nr=0;
        for(i=n; i>=1; --i)
        {
            s+=a[i][j];
            q.push(a[i][j]);
            ++nr;
            if(nr==l)
            {
                summ[i][j]=s;
                --nr;
                s-=q.front();
                q.pop();
            }
        }
    }
    for(i=n; i>=1; --i)
    {
        while(!q.empty())q.pop();
        s=0;
        nr=0;
        for(j=1; j<=i; ++j)
        {
            s+=a[i][j];
            q.push(a[i][j]);
            ++nr;
            if(nr==l)
            {
                lin[i][j]=s;
                --nr;
                s-=q.front();
                q.pop();
            }
        }
    }
    j=1;
    s=0;
    for(i=n-l+1; i<=n; ++i)
    {
        for(c=1; c<=j; ++c)
            s+=a[i][c];
        ++j;
    }
    li=n;
    for(i=n-l+1; i>=1; --i)
    {
        if(i!=n-l+1)
        {
            s=su;
            s-=lin[li][l];
            --li;
            s+=sum[i][1];
        }
        su=s;
        for(j=1; j<=i; ++j)
        {
            if(j!=1)s+=sum[i][j];
            ma=max(ma,S-s);
            s-=summ[i][j];
        }
    }
    printf("%d\n",ma);
    return 0;
}