package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	n, k     int
	pref     []int
	dpPrev   []int64
	dpCurr   []int64
	costL    int   = 1
	costR    int   = 0
	currCost int64 = 0
)

const INF int64 = 1e18



func getCost(l, r int) int64 {
	if l > r {
		return 0
	}

	
	for costR < r {
		costR++
		if costL <= costR-1 {
			rowOff := costR * (n + 1)
			currCost += int64(pref[rowOff+costR-1] - pref[rowOff+costL-1])
		}
	}
	
	for costL > l {
		costL--
		if costL+1 <= costR {
			rowOff := costL * (n + 1)
			currCost += int64(pref[rowOff+costR] - pref[rowOff+costL])
		}
	}
	
	for costR > r {
		if costL <= costR-1 {
			rowOff := costR * (n + 1)
			currCost -= int64(pref[rowOff+costR-1] - pref[rowOff+costL-1])
		}
		costR--
	}
	
	for costL < l {
		if costL+1 <= costR {
			rowOff := costL * (n + 1)
			currCost -= int64(pref[rowOff+costR] - pref[rowOff+costL])
		}
		costL++
	}
	return currCost
}


func solve(L, R, optL, optR int) {
	if L > R {
		return
	}

	mid := (L + R) >> 1
	bestP := -1
	minVal := INF

	limit := optR
	if mid-1 < limit {
		limit = mid - 1
	}

	
	for p := optL; p <= limit; p++ {
		if dpPrev[p] == INF {
			continue
		}
		val := dpPrev[p] + getCost(p+1, mid)
		if val < minVal {
			minVal = val
			bestP = p
		}
	}

	dpCurr[mid] = minVal
	
	
	pRec := bestP
	if pRec == -1 {
		pRec = optL
	}

	solve(L, mid-1, optL, pRec)
	solve(mid+1, R, pRec, optR)
}

func main() {
	
	scanner := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 256*1024)
	scanner.Buffer(buf, 64*1024*1024) 
	scanner.Split(bufio.ScanWords)

	readInt := func() int {
		scanner.Scan()
		b := scanner.Bytes()
		x := 0
		for _, c := range b {
			x = x*10 + int(c-'0')
		}
		return x
	}

	if !scanner.Scan() {
		return
	}
	
	
	b := scanner.Bytes()
	for _, c := range b {
		n = n*10 + int(c-'0')
	}
	k = readInt()

	
	pref = make([]int, (n+1)*(n+1))
	for i := 1; i <= n; i++ {
		rowOff := i * (n + 1)
		sum := 0
		for j := 1; j <= n; j++ {
			val := readInt()
			sum += val
			pref[rowOff+j] = sum
		}
	}

	dpPrev = make([]int64, n+1)
	dpCurr = make([]int64, n+1)

	
	for i := 1; i <= n; i++ {
		dpPrev[i] = INF
	}
	dpPrev[0] = 0

	
	for j := 1; j <= k; j++ {
		solve(j, n, j-1, n-1)
		copy(dpPrev, dpCurr)
	}

	fmt.Println(dpPrev[n])
}