#[allow(dead_code)] const MOD: usize = 1_000000000 + 7; fn main() { let mut cin = Scanner::new(); let n = cin.next_usize() - 1; let m = cin.next_usize(); let a = (0..m).map(|_| (0..m).map(|_| { cin.next_usize() }).collect::>()).collect::>(); let max = m*m+1; let mut dp = vec![vec![vec![0; m]; m]; max]; for k in 1..max { for i in 0..m { for j in 0..m { for l in 0..m { dp[k][i][j] = if k == 1 { std::cmp::max(dp[k][i][j], a[i][j]) } else { std::cmp::max(dp[k][i][j], dp[k-1][i][l] + a[l][j]) } } } } } let mut ans = 0; for k in 1..max { for i in 0..m { for j in 0..m { let q = n / k; let r = n % k; ans = std::cmp::max(ans, dp[k][i][i] * q + dp[r][i][j]); } } } println!("{}", ans); } struct Scanner { reader: std::io::Stdin, tokens: std::collections::VecDeque, } impl Scanner { fn new() -> Self { Scanner { reader: std::io::stdin(), tokens: std::collections::VecDeque::new(), } } fn next(&mut self) -> String { if self.tokens.is_empty() { let mut s = String::new(); loop { self.reader.read_line(&mut s).ok(); let s = s.trim(); if s.len() != 0 { for it in s.split_whitespace() { self.tokens.push_back(it.into()) } break; } } } self.tokens.pop_front().unwrap() } fn next_generics(&mut self) -> T where T: std::str::FromStr + std::marker::Copy, ::Err: std::fmt::Debug { self.next().parse().unwrap() } #[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next_generics::() } #[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next_generics::() } #[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next_generics::() } #[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next_generics::() } #[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next_generics::() } }