package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

const INF int64 = 1 << 60

type DEdge struct {
	to  int
	rev int
	cap int64
}

type Dinic struct {
	n     int
	g     [][]DEdge
	level []int
	it    []int
}

func NewDinic(n int) *Dinic {
	return &Dinic{
		n:     n,
		g:     make([][]DEdge, n),
		level: make([]int, n),
		it:    make([]int, n),
	}
}

func (d *Dinic) AddEdge(fr, to int, cap int64) int {
	fi := len(d.g[fr])
	ti := len(d.g[to])
	d.g[fr] = append(d.g[fr], DEdge{to: to, rev: ti, cap: cap})
	d.g[to] = append(d.g[to], DEdge{to: fr, rev: fi, cap: 0})
	return fi
}

func (d *Dinic) bfs(s, t int) bool {
	for i := 0; i < d.n; i++ {
		d.level[i] = -1
	}
	q := make([]int, 0, d.n)
	d.level[s] = 0
	q = append(q, s)
	for h := 0; h < len(q); h++ {
		v := q[h]
		for _, e := range d.g[v] {
			if e.cap > 0 && d.level[e.to] < 0 {
				d.level[e.to] = d.level[v] + 1
				q = append(q, e.to)
			}
		}
	}
	return d.level[t] >= 0
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func (d *Dinic) dfs(v, t int, f int64) int64 {
	if v == t {
		return f
	}
	for ; d.it[v] < len(d.g[v]); d.it[v]++ {
		i := d.it[v]
		e := &d.g[v][i]
		if e.cap > 0 && d.level[v] < d.level[e.to] {
			ret := d.dfs(e.to, t, min64(f, e.cap))
			if ret > 0 {
				e.cap -= ret
				d.g[e.to][e.rev].cap += ret
				return ret
			}
		}
	}
	return 0
}

func (d *Dinic) MaxFlow(s, t int) int64 {
	var flow int64
	for d.bfs(s, t) {
		for i := 0; i < d.n; i++ {
			d.it[i] = 0
		}
		for {
			f := d.dfs(s, t, INF)
			if f == 0 {
				break
			}
			flow += f
		}
	}
	return flow
}

type MEdge struct {
	to   int
	rev  int
	cap  int64
	cost int64
}

type MCMF struct {
	n int
	g [][]MEdge
}

func NewMCMF(n int) *MCMF {
	return &MCMF{
		n: n,
		g: make([][]MEdge, n),
	}
}

func (m *MCMF) AddEdge(fr, to int, cap, cost int64) {
	fi := len(m.g[fr])
	ti := len(m.g[to])
	m.g[fr] = append(m.g[fr], MEdge{to: to, rev: ti, cap: cap, cost: cost})
	m.g[to] = append(m.g[to], MEdge{to: fr, rev: fi, cap: 0, cost: -cost})
}

func (m *MCMF) AddEdgeResidual(fr, to int, fcap, rcap, cost int64) {
	fi := len(m.g[fr])
	ti := len(m.g[to])
	m.g[fr] = append(m.g[fr], MEdge{to: to, rev: ti, cap: fcap, cost: cost})
	m.g[to] = append(m.g[to], MEdge{to: fr, rev: fi, cap: rcap, cost: -cost})
}

type Item struct {
	d int64
	v int
}

type PQ []Item

func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool {
	return pq[i].d < pq[j].d
}
func (pq PQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[:n-1]
	return x
}

func (m *MCMF) ShortestPath(s int, pot []int64) ([]int64, []int, []int) {
	dist := make([]int64, m.n)
	pv := make([]int, m.n)
	pe := make([]int, m.n)
	for i := 0; i < m.n; i++ {
		dist[i] = INF
		pv[i] = -1
		pe[i] = -1
	}
	dist[s] = 0
	pq := &PQ{}
	heap.Init(pq)
	heap.Push(pq, Item{d: 0, v: s})
	for pq.Len() > 0 {
		it := heap.Pop(pq).(Item)
		if it.d != dist[it.v] {
			continue
		}
		v := it.v
		for i, e := range m.g[v] {
			if e.cap <= 0 {
				continue
			}
			nd := it.d + e.cost + pot[v] - pot[e.to]
			if nd < dist[e.to] {
				dist[e.to] = nd
				pv[e.to] = v
				pe[e.to] = i
				heap.Push(pq, Item{d: nd, v: e.to})
			}
		}
	}
	return dist, pv, pe
}

func (m *MCMF) Augment(s, t int, pv, pe []int, f int64) {
	for v := t; v != s; v = pv[v] {
		p := pv[v]
		i := pe[v]
		rev := m.g[p][i].rev
		m.g[p][i].cap -= f
		m.g[v][rev].cap += f
	}
}

type Orig struct {
	u   int
	v   int
	cap int64
	idx int
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	var k int64
	fmt.Fscan(in, &n, &k)

	d := NewDinic(n)
	origs := make([]Orig, 0)

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			var c int64
			fmt.Fscan(in, &c)
			if c > 0 {
				idx := d.AddEdge(i, j, c)
				origs = append(origs, Orig{u: i, v: j, cap: c, idx: idx})
			}
		}
	}

	base := d.MaxFlow(0, n-1)
	if k == 0 {
		fmt.Fprintln(out, base)
		return
	}

	m := NewMCMF(n)
	for _, e := range origs {
		flow := e.cap - d.g[e.u][e.idx].cap
		m.AddEdgeResidual(e.u, e.v, e.cap-flow, flow, 0)
		m.AddEdge(e.u, e.v, k, 1)
	}

	pot := make([]int64, n)
	var used int64
	var added int64

	for used < k {
		dist, pv, pe := m.ShortestPath(0, pot)
		if dist[n-1] >= INF/2 {
			break
		}

		pathCost := dist[n-1] + pot[n-1] - pot[0]
		for i := 0; i < n; i++ {
			if dist[i] < INF/2 {
				pot[i] += dist[i]
			}
		}

		f := INF
		for v := n - 1; v != 0; v = pv[v] {
			p := pv[v]
			i := pe[v]
			if p < 0 {
				f = 0
				break
			}
			if m.g[p][i].cap < f {
				f = m.g[p][i].cap
			}
		}
		if f == 0 {
			break
		}

		if pathCost > 0 {
			can := (k - used) / pathCost
			if can == 0 {
				break
			}
			if f > can {
				f = can
			}
			used += f * pathCost
		}

		m.Augment(0, n-1, pv, pe, f)
		added += f
	}

	fmt.Fprintln(out, base+added)
}