import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] def TSP(N, D, start): """ 巡回セールスマン問題 O(N^2*2^N) :param N: 頂点数 :param D: NxNの距離行列 :param start: 始点のindex :return: 最短距離 """ INF = 100 dp = [[INF] * (1<= INF: continue for v in range(N): if (case >> v) & 1: continue dp[v][case|(1< K: continue fixed.append(x) if len(fixed) > K+1: break n = len(fixed) FD = [[INF]*n for _ in range(n)] for i in range(n): for j in range(n): FD[i][j] = D[fixed[i]][fixed[j]] k = TSP(n, FD, 0) if k > K: fixed.pop() else: ans += A[x] print(ans) if __name__ == "__main__": main()