#include <bits/stdc++.h>
#define Dim 1005
using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");
int N,K,V[Dim][Dim],Tr[Dim][Dim];
int cnt,p=1,A[3][Dim][Dim];

struct info
{
    int line,dg;
}S[Dim][Dim];

int main()
{
    f>>N>>K;
    for(int i=1;i<=N;i++)
    for(int j=1;j<=i;j++)
    {
        f>>V[i][j];
        S[i][j].line=S[i][j-1].line+V[i][j];
        S[i][j].dg=S[i-1][j-1].dg+V[i][j];
    }
    for(int i=1;i<=N;i++)
    for(int j=i;j>=1;j--)
    {
        Tr[i][j]=Tr[i-1][j]+S[i][i].line-S[i][j-1].line;
        if(i>=K-1&&j==i-K+2)
        {
            A[1][i][j]=Tr[i][j];
             //cout<<i<<" "<<j<<" "<<A[1][i][j]<<'\n';
        }
    }

    for(int i=K;i<=N;i++)
    for(int j=1;j<=i-K+1;j++)
    {
        A[1][i][j]=A[1][i-1][j]+S[i][j+K-2].line-S[i][j-1].line-(S[i-1][j+K-2].dg-S[i-K][j-1].dg);
        //cout<<i<<" "<<j<<" "<<A[1][i][j]<<'\n';
    }
//cout<<'\n'<<'\n'<<'\n';
    for(int l=K;l<=N;l++)
    {
        cnt=0;
        for(int i=l;i<=N;i++)
        {
            cnt++;
            for(int j=1;j<=cnt;j++)
            {
                A[3-p][i][j]=Tr[i][j]-min(A[p][i][j],min(A[p][i-1][j],A[p][i][j+1]));
                //cout<<i<<" "<<j<<" "<<Tr[i][j]<<" "<<A[3-p][i][j]<<" "<<A[p][i][j]<<" "<<A[p][i-1][j]<<" "<<A[p][i][j+1]<<'\n';
            }
            if(p==2) p--;
            else p++;
        }
    }
    g<<A[3-p][N][1];
    return 0;
}