#include<iostream>
#include<algorithm>
using namespace std;
long A[40][40][40],B[40][40][40],n,m,ans;
main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)for(int j=0;j<m;j++)cin>>A[0][i][j];
	for(int i=0;i<39;i++)for(int x=0;x<m;x++)for(int y=0;y<m;y++)for(int z=0;z<m;z++)A[i+1][x][y]=max(A[i+1][x][y],A[i][x][z]+A[i][z][y]);
	n--;
	for(int i=0;i<39;i++)
	{
		if(n&(1L<<i))
		{
			for(int x=0;x<m;x++)for(int y=0;y<m;y++)
			{
				for(int z=0;z<m;z++)B[i+1][x][y]=max(B[i+1][x][y],B[i][x][z]+A[i][z][y]);
				ans=max(ans,B[i+1][x][y]);
			}
		}
		else
		{
			for(int x=0;x<m;x++)for(int y=0;y<m;y++)B[i+1][x][y]=B[i][x][y];
		}
	}
	cout<<ans<<endl;
}