Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))
AB.sort()

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print(min(DP[H:]))


### FIXED CODE ###

# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))
### BUGGY CODE ###

n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

# 上のコードだとTLE

# from scipy.sparse.csgraph import floyd_warshall
# M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))


### FIXED CODE ###

n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(1, n+1):
#     for i in range(1, n+1):
#         for j in range(1, n+1):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

from scipy.sparse.csgraph import floyd_warshall
M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
s = [0 for i in range(Q)]
t = 0
for i in range(Q):
    l,r = map(int,input().split())
    j = l-1
    for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            t += 1
    s[i] = t
    t = 0
for i in range(Q):
    print(s[i])

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
a =[0] * N
for i in range(N-1):
    if S[i] == "A" and S[i + 1] == "C":
        a[i + 1] = a[i] + 1
    else:
        a[i + 1] = a[i]
l, r = 0, 0
b = [0] * Q
for i in range(Q):
    l, r = map(int, input().split())
    b[i] = a[r-1] - a[l-1]
for i in range(Q):
    print(b[i])
### BUGGY CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

h,w = ma()
A = []
for i in range(h):
    A.append(lma())
B= []
for i in range(h):
    B.append(lma())
D = [[abs(A[i][j]-B[i][j]) for j in range(w)] for i in range(h)]
mx = 0
for i in range(h):
    for j in range(w):
        mx = max(mx,D[i][j])
prev = [[False]*((h+w)*mx+1) for j in range(w)]
nex = [[False]*((h+w)*mx+1) for j in range(w)]
prev[0][0]=True
for i in range(h):
    for j in range(w):
        d = D[i][j]
        if j==0:
            for k in range((h+w)*mx+1-d):
                nex[j][k+d] = nex[j][k+d] or prev[j][k]
                nex[j][abs(k-d)] = nex[j][abs(k-d)] or prev[j][k]
        else:
            for k in range((h+w)*mx+1-d):
                nex[j][k+d] = nex[j][k+d] or prev[j][k] or nex[j-1][k]
                nex[j][abs(k-d)] = nex[j][abs(k-d)] or prev[j][k] or nex[j-1][k]
    prev=nex
    nex=[[False]*((h+w)*mx+1) for j in range(w)]
for i in range((h+w)*mx+1):
    if prev[w-1][i]:
        print(i)
        exit()


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

h,w = ma()
A = []
for i in range(h):
    A.append(lma())
B= []
for i in range(h):
    B.append(lma())
D = [[abs(A[i][j]-B[i][j]) for j in range(w)] for i in range(h)]
mx = 0
for i in range(h):
    for j in range(w):
        mx = max(mx,D[i][j])

le = (h+w)*mx
prev = [0]*w
nex = [0]*w
prev[0]=prev[0] | 2**le
for i in range(h):
    for j in range(w):
        d = D[i][j]
        if j==0:
            nex[j] = nex[j] | prev[j]>>d |prev[j]<<d
        else:
            nex[j] = nex[j] | prev[j]>>d |prev[j]<<d
            nex[j] = nex[j] | nex[j-1]>>d |nex[j-1]<<d
        #print(i,j,d,bin(nex[j]))
    prev=nex
    nex = [0]*w
for i in range(le+1):
    if (prev[w-1]>>le+i &1) or (prev[w-1]>>le-i &1):
        print(i)
        exit()
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
c=[]
cnt=0
for i in range(1,N+1)[::-1]:
  if len([x for x in c if x%i==0])%2 != a[i-1]:
    a[i-1]=1
    c.append(i)
    cnt+=1
print(cnt)
if len(c)>0:
  print(*c,sep='\n')

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
c=[]
cnt=0
for i in range(1,N+1)[::-1]:
  if sum(b[i-1::i])%2 != a[i-1]:
    b[i-1]=1
    c.append(i)
    cnt+=1
print(cnt)
if len(c)>0:
  print(*c,sep='\n')
### BUGGY CODE ###

N = int(input())
S = input()
S = [0 if si == "#" else 1 for si in S]
def taskC(N,S):
    Wlist = []
    Blist = []
    Wcount = 0
    Bcount = 0
    S0 = S[0]
    for si in S:
        if si == 0:
            Bcount += 1
            if Wcount > 0:
                Wlist = [Wcount] + Wlist
                Wcount = 0
        else:
            Wcount += 1
            if Bcount >0:
                Blist += [Bcount]
                Bcount = 0
    Wlist = ([Wcount] + Wlist) if Wcount > 0 else Wlist
    Blist = (Blist + [Bcount]) if Bcount > 0 else Blist
    if len(Wlist)+len(Blist) <= 1:
        return 0
    if len(Wlist)>len(Blist):
        Wlist = Wlist[:-1]
        S0 = 0
    elif len(Blist)>len(Wlist):
        Blist = Blist[:-1]
        S0 = 0
    Wsum = [0]
    Bsum = [0]
    for ind in range(len(Wlist)):
        Wsum = [ Wsum[0] + Wlist[ind]] + Wsum
        Bsum += [ Bsum[-1] + Blist[ind]]
    ret = min([Wsum[i]+Bsum[i] for i in range(len(Wsum))])
    if S0 == 0:
        ret2 = min([Wsum[i]+Bsum[i+1] for i in range(len(Wsum)-1)])
        return min(ret, ret2)
    else:
        ret2 = min([Wsum[i+1]+Bsum[i] for i in range(len(Wsum)-1)])
        return min(ret, ret2)
print(taskC(N,S))


### FIXED CODE ###

N = int(input())
S = input()
Bsum = [0] #境界より左にある黒の数
Wsum = [0] #境界より右にある白の数
for i in range(N):
    Bsum += [Bsum[-1]+(1 if S[i]=="#" else 0) ]
    Wsum += [Wsum[-1]+(1 if S[N-i-1]=="." else 0)]
print(min([Bsum[i]+Wsum[N-i] for i in range(N+1)]))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

def dfs(p, x):
    global counter
    flag = False
    done = [True for _ in range(N)]
    done[0] = False
    if p == 0:
        counter[0] += x
        flag = True
    stack = deque(edge[0])
    while stack:
        s = stack.popleft()
        if done[s]:
            if s == p:
                flag = True
                while stack:
                    stack.pop()
            if flag:
                counter[s] += x
            done[s] = False
            for n in edge[s]:
                stack.append(n)
                
for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p - 1, x)

[print(c, end=" ") for c in counter]  

### FIXED CODE ###

N, Q = map(int, input().split())

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N + 1)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x

stack = [(0, -1)]
while stack:
    s, parent = stack.pop()
    counter[s] += counter[parent]
    for n in edge[s]:
        if n == parent:
            continue
        stack.append((n, s))

[print(c, end=" ") for c in counter[:N]]
### BUGGY CODE ###

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue0 = deque([[ch-1, cw-1, 0]])
queue1 = deque()
while queue0:  
  x,y,c=queue0.popleft()
  queue1.append((x,y,c))
  for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=c:
      continue
    temp[xtemp][ytemp]=c
    queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
    
  if len(queue0)==0:      
    while queue1:
      x,y,c=queue1.popleft()
      for i,j in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        xtemp,ytemp=x+i,y+j
        if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
          continue
        if temp[xtemp][ytemp]<=c+1:
          continue
        temp[xtemp][ytemp]=c+1
        queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
        
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

### FIXED CODE ###

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue0 = deque([[ch-1, cw-1, 0]])
queue1 = deque()
while queue0:  
  x,y,c=queue0.popleft()
  queue1.append((x,y,c))
  for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=c:
      continue
    temp[xtemp][ytemp]=c
    queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
    
  if len(queue0)==0:      
    while queue1:
      x,y,c=queue1.popleft()
      for i,j in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        xtemp,ytemp=x+i,y+j
        if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
          continue
        if temp[xtemp][ytemp]<=c+1:
          continue
        temp[xtemp][ytemp]=c+1
        queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
        
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

s = []
for i in range(n):
  k = 0
  for j in range(n):
    if (i==j):
      continue
    k = k^a[j]
  s.append(k)
  
print(*s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

x = 0
for i in a:
  x ^= i

s = [x^j for j in a]
  
print(*s)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    check = [False] * N
    index = 0
    ans = 0
    cnt = 0
    while True:
        pre = -1
        for i in range(index,N,1):
            if check[i]:
                continue
            if A[i] > pre:
                pre = A[i]
                check[i] = True
                cnt += 1
            else:
                cnt = min(cnt,i)

        ans += 1
        if cnt == N:
            break
    
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
from bisect import bisect_left

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    d = deque([])
    d.append(A[0])
    for i in range(1,N):
        p = bisect_left(d, A[i])
        if p == 0:
            d.appendleft(A[i])
        else:
            d[p-1] = A[i]

    print(len(d))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
  for k in range(W+1):
    if w[i]<=k:
      dp[i+1][k] = max(dp[i][k-w[i]]+v[i],dp[i][k])
    else:
      dp[i+1][k] = dp[i][k]

print(dp[-1][-1])


### FIXED CODE ###

N,W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
  for k in range(W+1):
    if w[i]<=k:
      dp[i+1][k] = max(dp[i][k-w[i]]+v[i],dp[i][k])
    else:
      dp[i+1][k] = dp[i][k]

print(dp[-1][-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#%%
def dfs(gr,li):
    st = []
    seen = set()
    st.append([0,-1])
    while(st):
        x,fr = st.pop()
        if(x in seen):continue
        seen.add(x)
        if(fr != -1):
            li[x]+=li[fr]
            if(len(gr[x])==1):
                continue
        for i in gr[x]:
            if(i==fr):continue
            st[0:0] = [[i,x]]

#%%
def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = input().split()
        li[int(p)-1] += int(x)

    dfs(gp,li)
    print(*li)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = input().split()
        li[int(p)-1] += int(x)

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

if __name__ == '__main__':
    main()
### BUGGY CODE ###




N, K = map(int, input().split())


dices = list(map(int, input().split()))

# 制約より
MAX_DICE = 1000*K

# 0-K番目を初期としてK個の値が最大になる範囲を探す
pos = 0
maxpos = pos
maxvalue = sum(dices[maxpos:maxpos+K])

for pos in range(1, N-K+1):
    if sum(dices[pos:pos+K]) > maxvalue:
        maxpos = pos
        maxvalue = sum(dices[pos:pos+K])

        # 上限
        if maxvalue == MAX_DICE:
            break

# 期待値を合計する
ans = 0
for dice in dices[maxpos:maxpos+K]:
    ans += (dice+1)/2


print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
ary = list(map(int, input().split()))


# ruisekiwa
ruiseki = [0] * (n+1)

for i, x in enumerate(ary):
    ruiseki[i+1] = ruiseki[i] + x

kmax = 0
for i in range(n+1-k):
    ksum = ruiseki[i+k] - ruiseki[i]
    kmax = max(kmax, ksum)

print((kmax+k) / 2)
### BUGGY CODE ###

n, m = map(int, input().split())
shop = []
for i in range(n):
    shop.append(list(map(int, input().split())))
shop.sort()
for i in range(n):
    tot_b = 0
    for j in range(i+1):
        tot_b += shop[j][1]
    if tot_b >= m:
        break
if tot_b == m:
    cost = 0
    for k in range(i+1):
        cost += shop[k][0]*shop[k][1]
    print(cost)
if tot_b > m:
    cost = 0
    for k in range(i):
        cost+= shop[k][0]*shop[k][1]
    cost += shop[i][0]*(shop[i][1]+m-tot_b)
    print(cost)



### FIXED CODE ###

n, m = map(int, input().split())
shop = []
for i in range(n):
    shop.append(list(map(int, input().split())))
shop.sort()
i = 0
tot_b = 0
while tot_b < m:
    tot_b += shop[i][1]
    i += 1
i -= 1
if tot_b == m:
    cost = 0
    for k in range(i+1):
        cost += shop[k][0]*shop[k][1]
    print(cost)
if tot_b > m:
    cost = 0
    for k in range(i):
        cost+= shop[k][0]*shop[k][1]
    cost += shop[i][0]*(shop[i][1]+m-tot_b)
    print(cost)
### BUGGY CODE ###

N,K = map(int, input().split())
P=[(int(x)+1)/2 for x in input().split()]
max=0
for i in range(N-K+1):
    kitai=0
    for k in range(K):
        kitai+=P[i+k]
    if max<kitai:
        max=kitai
print(max)


### FIXED CODE ###

N,K = map(int, input().split())
P=[(float(x)+1)/2 for x in input().split()]
#print(P)
max=0
kitai=0
for i in range(K):
    kitai+=P[i]
max=kitai
for i in range(N-K):
    kitai-=P[i]
    kitai+=P[i+K]
    if max<kitai:
        max=kitai
print(max)
### BUGGY CODE ###

import sys
from sys import stdin
n = int(stdin.readline().rstrip())
a = [int(stdin.readline().rstrip()) for x in range(n)]
for i in range(len(a)):
    b = []
    b.append(a[:i])
    b.append(a[i+1:])
    b = [flatten for inner in b for flatten in inner]
    print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for x in range(n)]
b = sorted(a,reverse=True)
for i in range(n):
    if b[0] == a[i]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

def resolve():
    N, A, B = map(int, input().split())  

    MAX_COUNT = 10**(100)
    ao_count = 0

    for i in range(MAX_COUNT):
        if A <= N:
            ao_count += A
            N -= A
        else:
            ao_count += N
            print(ao_count)
            return

        if B <= N:
            N -= B
        else:
            print(ao_count)
            return



if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N, A, B = map(int, input().split())  

    ao_count = 0

    count_num = N // (A + B)
    amari_num = N % (A + B)



    ao_count = count_num * A

    if A <= amari_num:
        ao_count += A
    else:
        ao_count += amari_num

    print(ao_count)



if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = float('inf')

for i in range(n-1):
    ans = min(ans,abs(sum(a[0:i+1])-sum(a[i+1:])))

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
x = 0
y = sum(l)
xy = [10**15]*n
for i in range(n-1):
    x += l[i]
    y -= l[i]
    xy[i] = abs(x-y)
print(min(xy))
### BUGGY CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


N = int(input())
A = [int(input()) for i in range(N)]
mod = 998244353
ans = pow(3, N, mod)
sum_A = sum(A)
dp = dp_table(N, sum_A + 1)
# dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

# init
dp[0][A[0]] = 1
dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

# init2
dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
dp2[0][A[0]] = 1
dp2[0][0] = 1  # 今度は片方に集中したパターン

# dp
sum_now = A[0]
for i in range(1, N):
    a = A[i]
    sum_now += a
    for length in range(0, sum_now+1):
        # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
        if length >= a:
            dp[i][length] = dp[i - 1][length - a] + dp[i - 1][length] * 2
        else:
            dp[i][length] = dp[i-1][length]*2
        while (dp[i][length] > mod):
            dp[i][length] -= mod
        #dp[i][length] %= mod

    for length in range(min(sum_now + 1, sum_A // 2 + 1)):
        if length >= a:
            dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
        else:
            dp2[i][length] = dp2[i-1][length]
        while (dp2[i][length] > mod):
            dp2[i][length] -= mod
        #dp2[i][length] %= mod
# print(sum(dp[N-1][sum_A//2]))
# print(dp)
ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
if sum_A % 2 == 0:
    ans += 3*dp2[N-1][sum_A//2]
print(ans % mod)


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()