def mul(a,b)
	r=a.size.times.map{[0]*b[0].size}
	a.size.times{|y|
		b[0].size.times{|x|
			r[y][x]=b.size.times.reduce(0){|s,i|[s,a[y][i]+b[i][x]].max}
		}
	}
	r
end
n=gets.to_i-1
m=gets.to_i
e=m.times.map{|i|[0]*m}
a=$<.map{|e|e.split.map &:to_i}
while n>0
	e=mul(e,a) if n%2>0
	a=mul(a,a)
	n/=2
end
p e.map(&:max).max