maehrm

N = int(input())
A = list(map(int, input().split()))
s = sum(A)
dp = 1
for i in range(N):
    dp |= dp << A[i]
ans = (s + 1) // 2
while ans <= 2000 * 2000 + 1:
    if (dp >> ans) & 1:
        break

maehrm

INF = 10**10

N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = [INF] * N  # dp[i]:町iの上流をたどって見たとき、金1kgを買える最安値
G = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    G[x].append(y)

maehrm

import sys

sys.setrecursionlimit(10**7)
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
MOD = 10**9 + 7


def dfs(x, y):
    if dp[y][x] != 0:
        return dp[y][x]

maehrm

for g in range(12):
    s = set()
    i = 0
    while True:
        v = (g * i) % 12
        if v in s:
            break
        s.add(v)
        i += 1
    print(f"<{g:>2}> =  {s}")

maehrm

import sys

sys.setrecursionlimit(10**7)


def dfs(v):
    if dp[v] != -1:             # 調査済み
        return dp[v]
    ret = 0
    for nxt in G[v]:

maehrm

idx = [-1] * 1609
fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

def ask(i):
    if idx[i] == -1:
        print("?", i)
        idx[i] = int(input())
    return idx[i]

def solv():

maehrm

N = int(input())
S = input()
T = input()
MOD = 699999953
seq1 = [0] * N
seq3 = [0] * N
for i in range(N):
    if S[i] == "G":
        seq1[i] = 1
    elif S[i] == "B":

maehrm

S = 1 << 1 | 1 << 3 | 1 << 5  # S = {1, 3, 5}
N = 6  # 6ビット使用するため
PS = S  # 集合Sの冪集合PSを求める。
ans = [[]]  # 空集合は含めておく
while PS > 0:
    tmp = []
    for i in range(N):
        if (PS >> i) & 1:
            tmp.append(i)
    ans.append(tmp)

maehrm

N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a][b] = True
    G[b][a] = True

ok = [True] * (1 << N)  # 各頂点が繋がっているかどうか?
for bit in range(1 << N):
    vs = []

maehrm

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
cst = [0] * (1 << N)
for msk in range(1 << N):       # あらかじめmskグループのときの点数をcstに求めておく
    for i in range(N):
        for j in range(i + 1, N):
            if (msk & (1 << i)) and (msk & (1 << j)):
                cst[msk] += a[i][j]
for msk in range(1 << N):