import sys
input = sys.stdin.readline

def calc(A, B):
    res = [[0]*m for _ in range(m)]
    
    for i in range(m):
        for j in range(m):
            for k in range(m):
                res[i][j] = max(res[i][j], A[i][k]+B[k][j])
    
    return res

n = int(input())-1
m = int(input())
A = [list(map(int, input().split())) for _ in range(m)]
now = [[0]*m for _ in range(m)]

while n:
    if n&1:
        now = calc(now, A)
    
    n >>= 1
    A = calc(A, A)

ans = 0

for i in range(m):
    for j in range(m):
        ans = max(ans, now[i][j])

print(ans)