#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll dp[31][31][34];
ll memo[31][31][34];
int m;
ll solve(ll n, int x, int y, int t){
	if(n==0) return 0;
	if(memo[x][y][t]) return memo[x][y][t];
	int i0;
	for(int i=33; i>=0; i--){
		if(n&(1ll<<i)){
			i0=i;
			break;
		}
	}
	if(n==(1ll<<i0)) return memo[x][y][t]=dp[x][y][i0];
	ll ans=0;
	for(int z=0; z<m; z++){
		ans=max(ans, dp[x][z][i0]+solve(n-(1ll<<i0), z, y, t+1));
	}
	return memo[x][y][t]=ans;
}
int main()
{
	ll n;
	cin>>n>>m;
	int a[30][30];
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<=33; k++){
				dp[i][j][k]=-1;
			}
		}
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			cin>>a[i][j];
			dp[i][j][0]=a[i][j];
		}
	}
	for(int i=0; i<33; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<m; k++){
				for(int l=0; l<m; l++){
				    if(dp[j][l][i]==-1 || dp[l][k][i]==-1) continue;
					dp[j][k][i+1]=max(dp[j][k][i+1], dp[j][l][i]+dp[l][k][i]);
				}
			}
		}
	}
	ll ans=0;
	for(int x=0; x<m; x++){
		for(int y=0; y<m; y++){
			ans=max(ans, solve(n-1, x, y, 0));
		}
	}
	cout<<ans<<endl;
	return 0;
}