#include <iostream>
#include <fstream>

using namespace std;

int N, K, T, M, Temp, S;
const int nmax = 1024;
int A[nmax][nmax], D[nmax][nmax], R[nmax][nmax], C[nmax][nmax];

int main()
{
    ifstream in ("ferma2.in");

    in >> N >> K;
    int i, j, w;
    for(i = 1; i <= N; i++)
        for(j = 1; j <= i; j++)
        {
            in >> A[i][j];
            T += A[i][j];
        }

    K = N - K;
    for(i = 1; i <= N - K + 1; i++)
    {
        /** diag **/
        for(w = 0; w < K; w++)
            D[i][1] += A[i + w][w + 1];

        for(w = 1; w + i <= N - K + 1; w++)
            D[i + w][w + 1] = D[i + w - 1][w] - A[i + w - 1][w] + A[i + w + K - 1][w + K];

        /** coloana **/
        for(w = 0; w < K; w++)
            C[i][i] += A[i + w][i];

        for(w = 1; w + i <= N - K + 1; w++)
            C[i + w][i] = C[i + w - 1][i] - A[i + w - 1][i] + A[i + w + K - 1][i];

        /** rand **/
        for(w = 0; w < K; w++)
            R[N - i + 1][1] += A[N - i + 1][w + 1];

        for(w = 1; w + i <= N - K + 1; w++)
            R[N - i + 1][w + 1] = R[N - i + 1][w] - A[N - i + 1][w] + A[N - i + 1][w + K];
    }

    int pas = 1;
    for(i = N - K + 1; i <= N; i++, pas++)
        for(j = 1; j <= pas; j++)
            M += A[i][j];

    Temp = M;
    for(i = 1; i <= N - K + 1; i++)
    {
        S = Temp;
        for(j = N; j > K + i - 1; j--)
        {
            S = S - R[j][i] + D[j - K][i];
            if(S < M)
                M = S;
        }
        if(N == j + K - 1)
            break;
        Temp = Temp - C[N - K + 1][i] + D[N - K + 1][i + 1];
        if(Temp < M)
            M = Temp;
    }

    ofstream out("ferma2.out");
    out << T - M;
    return 0;
}