def gl
  $stdin.gets.chomp
end

N = gl.to_i
M = gl.to_i

scores = (0...M).map{ gl.split(" ").map{ |a| a.to_i } }
routes = [scores]
(M-1).times { |i|
  route = (0...M).map{ |i|
    (0...M).map{ |j|
      (0...M).map{ |k| routes[-1][i][k] + routes[0][k][j] }.max
    }
  }
  routes << route
}

#routes.each_with_index { |h,i|
#  p i+1
#  h.each{ |r| p r }
#}

N0 = N-1
puts (0..[M,N0].min).map { |d|
  next 0 if d == 1
  (0...M).map { |i|
    if d == 0
      next (0...M).map{ |j| routes[[M,N0].min-1][i][j] }.max
    end

    l = N0 / d
    r = N0 % d
    mid = routes[d-1][i][i] * l
    edge = (0..r).map{ |a|
      b = r - a
      ((0...M).map{ |j| a > 0 ? routes[a-1][j][i] : 0 }.max || 0) + ((0...M).map{ |j| b > 0 ? routes[b-1][i][j] : 0 }.max || 0).tap{ |v|
        #p [mid, v+mid, [d,i,l,r,a,b]]
      }
    }.max
    mid + (edge || 0)
  }.max
}.max