import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class partition {

	public static void main(String[] args) throws Exception {
		//BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    	//PrintWriter w = new PrintWriter(System.out);

    	BufferedReader r = new BufferedReader(new FileReader("partition.in"));
    	PrintWriter w = new PrintWriter(new BufferedWriter(new FileWriter("partition.out")));

    	StringTokenizer st = new StringTokenizer(r.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int fences = Integer.parseInt(st.nextToken());

    	int[][] values = new int[n][n];

    	for (int i = 0; i < n; i++) {
    		st = new StringTokenizer(r.readLine());
    		for (int j = 0; j < n; j++) {
    			values[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}

    	int answer = 100000000;
    	for (int i = 0; i < (1 << (n - 1)); i++) {
    		if (setBits(i) > fences) continue;

    		boolean[] set = new boolean[n]; //set[i] means that line before i is set.
    		for (int j = 0; j < n - 1; j++) {
    			if ((i & 1 << j) > 0) {
    				set[j + 1] = true;
    			}
    		}

    		int start = 0;
    		int end = 100000000;

    		while (start <= end) {
    			int mid = (start + end) / 2;

    			boolean possible = true;
    			int linesLeft = fences - setBits(i);
        		int[] sections = new int[setBits(i) + 1];
        		int counter = 0;
        		for (int j = 0; j < n; j++) {
        			if (!set[j]) {
        				sections[counter] += values[j][0];
        			} else {
        				sections[++counter] += values[j][0];
        			}
        		}

        		for (int j = 1; j < n; j++) {
        			//Consider adding a vertical line before j.
        			for (int k = 0; k < sections.length; k++) {
        				if (sections[k] > mid) {
        					possible = false;
        					break;
        				}
        			}

        			counter = 0;
        			for (int k = 0; k < n; k++) {
        				if (!set[k]) {
            				sections[counter] += values[k][j];
            			} else {
            				sections[++counter] += values[k][j];
            			}
        			}

        			boolean setLine = false;
        			for (int k = 0; k < sections.length; k++) {
        				if (sections[k] > mid) {
        					//set the line before j
        					setLine = true;
        					break;
        				}
        			}

        			counter = 0;
        			if (setLine && linesLeft > 0) {
        				linesLeft--;
        				for (int k = 0; k < sections.length; k++) sections[k] = 0;
        				for (int k = 0; k < n; k++) {
        					if (!set[k]) {
                				sections[counter] += values[k][j];
                			} else {
                				sections[++counter] += values[k][j];
                			}
        				}
        				for (int k = 0; k < sections.length; k++) {
            				if (sections[k] > mid) {
            					possible = false;
            					break;
            				}
            			}
        			} else {
        				for (int k = 0; k < sections.length; k++) {
            				if (sections[k] > mid) {
            					possible = false;
            					break;
            				}
            			}
        			}
        		}

    			if (!possible) {
    				start = mid + 1;
    			} else {
    				end = mid - 1;
    			}
    		}

    		answer = Math.min(answer, start);
    	}

    	w.println(answer);
    	w.flush();
	}

	public static int setBits(int n) {
		int answer = 0;

		while (n != 0) {
			answer += n & 1;
			n >>= 1;
		}

		return answer;
	}

}