def f(X, Y):
    temp = [[0] * M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            for k in range(M):
                temp[i][j] = max(temp[i][j], X[i][k] + Y[k][j])
    return temp

N = int(input()) - 1
M = int(input())
A = []
for i in range(M):
    A.append(list(map(int, input().split())))

now = [[0] * M for _ in range(M)]
for i in range(35):
    if (N >> i) & 1:
        now = f(now, A)
    A = f(A, A)
ans = 0
for i in range(M):
    ans = max(ans, max(now[i]))

print(ans)