Untitled

import java.io.*;
import java.util.*; 
import java.lang.Math;
import static java.util.stream.Collectors.joining; 
import static java.util.stream.Collectors.toList;

public class Solution {

    // Function to get maximum sum of beauties of two non-intersecting sub-grids

    public static int get_ans(int N, List<List<Integer>> A) {
        int[][] grid = new int[N][N];
        
        // Convert the List to a 2D Array for easier manipulation
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = A.get(i).get(j);
            }
        }

        // Precompute the prefix sums of the grid
        int[][] prefixSum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                prefixSum[i][j] = grid[i - 1][j - 1] 
                                + prefixSum[i - 1][j] 
                                + prefixSum[i][j - 1] 
                                - prefixSum[i - 1][j - 1];
            }
        }

        int K = Math.min(N, N);  // Assuming the maximum number of non-overlapping sub-grids is the minimum of N as size of S is K or N

        // Initialize the DP array where dp[k][j] is the maximum beauty using exactly k sub-grids till column j
        int[][] dp = new int[K + 1][N + 1];
        
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE/2);
        }
        
        dp[0][0] = 0;

        // Calculate the DP array
        for (int col = 1; col <= N; col++) {
            for (int k = 1; k <= K; k++) {
                for (int size = 1; size <= N; size++) {
                    for (int si = 0; si + size <= N; si++) {
                        for (int sj = 0; sj + size <= col; sj++) {
                            int ei = si + size - 1;
                            int ej = sj + size - 1;
                            int subGridSum = getSum(prefixSum, si, sj, ei, ej);
                            dp[k][col] = Math.max(dp[k][col], dp[k - 1][sj] + subGridSum);
                        }
                    }
                }
            }
        }

        int maxBeauty = Integer.MIN_VALUE;
        for (int j = 0; j <= N; j++) {
            maxBeauty = Math.max(maxBeauty, dp[K][j]);
        }

        if (maxBeauty < 0) {
            maxBeauty += 1000000;
        }

        return maxBeauty;
    }

    // Compute the sum of sub-grid using precomputed prefix sums
    private static int getSum(int[][] prefixSum, int si, int sj, int ei, int ej) {
        return prefixSum[ei + 1][ej + 1] - prefixSum[ei + 1][sj] 
             - prefixSum[si][ej + 1] + prefixSum[si][sj];
    }
    

    public static void main(String[] args) {
        Scanner scan = new Scanner (System.in);
        int N = Integer.parseInt(scan.nextLine().trim());
        int K = Integer.parseInt(scan.nextLine().trim());
        List<List<Integer>> A = new ArrayList<>(N);
        
        for (int i = 0; i < N; i++) {
            A.add(
                Arrays.asList(scan.nextLine().trim().split(" "))
                .stream().map(s -> Integer.parseInt(s)).collect(toList())
                );
        }

        int result = get_ans(N, A);
        System.out.println(result);
    }
}