import sys

INF = 1e18

def multiply(A, B, m):
    B_transposed = [[B[k][j] for k in range(m)] for j in range(m)]
    res = [[-INF for _ in range(m)] for __ in range(m)]
    for i in range(m):
        a_row = A[i]
        for j in range(m):
            max_val = -INF
            b_col = B_transposed[j]
            for k in range(m):
                a = a_row[k]
                if a == -INF:
                    continue
                b = b_col[k]
                if b == -INF:
                    continue
                current = a + b
                if current > max_val:
                    max_val = current
            res[i][j] = max_val
    return res

def matrix_power(mat, power, m):
    result = [[-INF for _ in range(m)] for __ in range(m)]
    for i in range(m):
        result[i][i] = 0
    current_mat = [row[:] for row in mat]
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, current_mat, m)
        current_mat = multiply(current_mat, current_mat, m)
        power = power // 2
    return result

def vector_mult(v, mat, m):
    res = [-INF for _ in range(m)]
    for j in range(m):
        max_val = -INF
        for k in range(m):
            if v[k] == -INF or mat[k][j] == -INF:
                continue
            current = v[k] + mat[k][j]
            if current > max_val:
                max_val = current
        res[j] = max_val
    return res

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    m = int(input[ptr])
    ptr += 1
    if n == 1:
        print(0)
        return
    
    A = []
    for _ in range(m):
        row = list(map(int, input[ptr:ptr+m]))
        ptr += m
        A.append(row)
    
    T = [[-INF for _ in range(m)] for __ in range(m)]
    for i in range(m):
        for j in range(m):
            if i != j:
                T[i][j] = A[i][j]
    
    e = n - 1
    M = matrix_power(T, e, m)
    
    v0 = [0 for _ in range(m)]
    v_final = vector_mult(v0, M, m)
    
    max_score = max(v_final)
    print(int(max_score))

if __name__ == "__main__":
    main()