```go
package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(in, &n, &k)

	grid := make([][]byte, n)
	for i := 0; i < n; i++ {
		var s string
		fmt.Fscan(in, &s)
		grid[i] = []byte(s)
	}

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		for j := range dp[i] {
			dp[i][j] = 1 << 30
		}
	}

	if grid[0][0] == 'a' {
		dp[0][0] = 0
	} else {
		dp[0][0] = 1
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				continue
			}
			cost := 0
			if grid[i][j] != 'a' {
				cost = 1
			}
			if i > 0 && dp[i-1][j]+cost < dp[i][j] {
				dp[i][j] = dp[i-1][j] + cost
			}
			if j > 0 && dp[i][j-1]+cost < dp[i][j] {
				dp[i][j] = dp[i][j-1] + cost
			}
		}
	}

	maxDist := -1
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if dp[i][j] <= k && i+j > maxDist {
				maxDist = i + j
			}
		}
	}

	var res string
	var current [][2]int

	if maxDist == -1 {
		res = string(grid[0][0])
		current = append(current, [2]int{0, 0})
	} else {
		res = strings.Repeat("a", maxDist+1)
		for i := 0; i < n; i++ {
			j := maxDist - i
			if j >= 0 && j < n && dp[i][j] <= k {
				current = append(current, [2]int{i, j})
			}
		}
	}

	if maxDist == 2*n-2 {
		fmt.Println(res)
		return
	}

	startDist := maxDist
	if startDist == -1 {
		startDist = 0
	}

	vis := make([][]int, n)
	for i := range vis {
		vis[i] = make([]int, n)
	}
	mark := 1

	for d := startDist; d < 2*n-2; d++ {
		minChar := byte('z' + 1)
		var next [][2]int

		for _, cell := range current {
			i, j := cell[0], cell[1]

			if j+1 < n {
				ni, nj := i, j+1
				c := grid[ni][nj]
				if c < minChar {
					minChar = c
					next = [][2]int{{ni, nj}}
					vis[ni][nj] = mark
				} else if c == minChar && vis[ni][nj] != mark {
					next = append(next, [2]int{ni, nj})
					vis[ni][nj] = mark
				}
			}

			if i+1 < n {
				ni, nj := i+1, j
				c := grid[ni][nj]
				if c < minChar {
					minChar = c
					next = [][2]int{{ni, nj}}
					vis[ni][nj] = mark
				} else if c == minChar && vis[ni][nj] != mark {
					next = append(next, [2]int{ni, nj})
					vis[ni][nj] = mark
				}
			}
		}

		res += string(minChar)
		current = next
		mark++
	}

	fmt.Println(res)
}
```