I ovaj zadatak rješavamo isprobavanjem svih mogućnosti: za sve moguće početne pozicije \((i, j)\) Markovog odabira i sve moguće početne pozicije \((r, s)\) Darkovog odabira, provjeravamo koliki bi bio zbroj odabranih polja i uspoređujemo ga s dosad najvećim pronađenim zbrojem (varijablom maks). Na samom početku maks valja postaviti npr. na \(-50 \cdot 2K\), jer ako su svi brojevi u tablici negativni, maksimum može biti i negativan.

Unutar ugnježđene for-petlje koja bira sve moguće \(i, j, r, s\) valja zbrojiti \(K\) polja u \(i\)-tom retku počevši od polja \((i, j)\) te \(K\) polja u \(s\)-tom stupcu počevši od polja \((r, s)\). Od toga zbroja valja oduzeti zajedničko polje ako se odabiri "sijeku", jer bismo ga inače pribrojili dvaput. Za detalje pogledajte priloženi kod.

Rješenje

n, k = map(int, input().split())
a = []
for i in range(n):
    a.append([])
    redak = input().split()
    for broj in redak:
        a[-1].append(int(broj))

maks = -50 * 2 * k
for i in range(n):
    for j in range(n - k + 1):
        for r in range(n - k + 1):
            for s in range(n):
                zbroj = 0
                for x in range(k):
                    zbroj += a[i][j + x]
                    zbroj += a[r + x][s]
                if r <= i < r + k and j <= s < j + k:
                    zbroj -= a[i][s]
                maks = max(maks, zbroj)

print(maks)