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

N , Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

# 最小値を求める問題なのでinfで初期化
# dp[i][sun_a][sum_b]で考えていく
dp = [[[float('inf') for _ in range(10 * N + 1)] for _ in range(10 * N + 1)] for _ in range(N+1)]

# 初期選択状態を0とする

dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if dp[i][j][k] == float('inf'):
                continue
            
            # 選ばなかった場合
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            # 選んだ場合
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i])


ans = float('inf')
# 0スタートは何を選んでいない状態となり最小値が0になってしまうため1から開始する

# TLEになったため変更
#for i in range(1,10 * N + 1):
#    for j in range(1,10 * N + 1):
#        if i * Mb != j * Ma:
#            continue
#        ans = min(ans, dp[N][i][j])
#

for i in range(1, 10*N+1):
        if i*Ma>10*N or i*Mb>10*N:
            break
        ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N , Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

# TLEになってしまうためinfを5000とかで設定する
INF = 5000

# 最小値を求める問題なのでinfで初期化
# dp[i][sun_a][sum_b]で考えていく
dp = [[[INF for _ in range(10 * N + 1)] for _ in range(10 * N + 1)] for _ in range(N+1)]

# 初期選択状態を0とする

dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if dp[i][j][k] == INF:
                continue
            
            # 選ばなかった場合
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            # 選んだ場合
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i])


ans = INF
# 0スタートは何を選んでいない状態となり最小値が0になってしまうため1から開始する

# TLEになったため変更
#for i in range(1,10 * N + 1):
#    for j in range(1,10 * N + 1):
#        if i * Mb != j * Ma:
#            continue
#        ans = min(ans, dp[N][i][j])
#

for i in range(1, 10*N+1):
        if i*Ma>10*N or i*Mb>10*N:
            break
        ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n, W = list(map(int, input().split()))
w = [0 for i in range(n)]
v = [0 for i in range(n)]
for i in range(n):
    w[i], v[i] = list(map(int, input().split()))
dp = [[0 for i in range(W +1)] for j in range(n)]
for j in range(W+1):
    for i in range(n):
        p = j - w[i]
        s = dp[i - 1][j]
        if p >= 0:
            dp[i][j] = max(s, dp[i - 1][p] + v[i])
        else:
            dp[i][j] =  s
print(dp[-1][-1])


### FIXED CODE ###

n, W = list(map(int, input().split()))
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
for i in range(n):
    w[i + 1], v[i + 1] = list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,W+1):
        if w[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print(int(dp[n][W]))
### BUGGY CODE ###

N=int(input())
s=[]
cnt=0
for i in range(N):
    s.append(input())
s=list(map(sorted,s))
for j in range(N-1):
    for k in range(j+1,N):
        if s[j]==s[k]:
            cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
dic={}
cnt=0
for i in range(N):
    temp=' '.join(sorted(input()))
    if temp in dic:
        dic[temp]+=1
    else:
        dic[temp]=1
for k,v in dic.items():
    cnt+=v*(v-1)//2
print(cnt)
### BUGGY CODE ###

def have_AC(str):
    count=0
    for i in range(len(str)-1):
        if(str[i:i+2]=="AC"):
            count=count+1
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]

for i in range(q):
    a,b=input().split()
    a=int(a) -1
    b=int(b)
    num.append(have_AC(s[a:b]))

for j in range(len(num)):
    print(num[j])

### FIXED CODE ###

def have_AC(str):
    count=[0]
    for i in range(1,len(str)):
        if(str[i]=='C' and str[i-1]=='A'):
            count.append(count[i-1]+1)
            continue
        count.append(count[i-1])
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]
d=have_AC(s)

for i in range(q):
    a,b=input().split()
    a=int(a)
    b=int(b)
    num.append(d[b-1]-d[a-1])

for j in range(len(num)):
    print(num[j])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
      dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
      dp[i]=0
print(dp[n])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = input().split()

ans = {}
for x in set(A):
    a = A[:]
    a.remove(x)
    t = 0
    for y in set(a):
        m = a.count(y)
        t += m * (m - 1) // 2
    ans[x] = t

for x in A:
    print(ans[x])


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())
A = input().split()
a = Counter(A)

ans_all = 0
for x in a.keys():
    m = a[x]
    ans_all += m * (m - 1) // 2

for x in A:
    m = a[x] - 1
    print(ans_all - m)
### BUGGY CODE ###

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

pairs = []
for i in range(N):
    pairs.append(list(map(int, input().split())))

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

not_done = [True for _ in range(M)]

for A, B in pairs:
    for i in range(M-A, -1, -1):
        if not_done[i]:
            out += B
            #print(A, B)
            not_done[i] = False
            break

print(out)

### FIXED CODE ###

#input = raw_input
#import numpy as np

from heapq import heappush, heappop

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)
### BUGGY CODE ###

N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
                           
for a in range(N+1):
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      dp[a].append([[0]*(c+1) for i in range(b+1)])
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(b):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(max(1,b)):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)
### BUGGY CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])

### FIXED CODE ###

# atcoderのテスト用
# ./iunput/input.txt に入力を書き込む
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
V = max(v)
vmax = 10**5+1
# dp[i][sum_v] 
# := i-1番目までの品物で価値がsum_vを超えないように選んだときの重さの総和の最小値
# 価値の合計はどれくらい大きくなるかわからないので十分に用意しとく
dp = [[inf for _ in range(vmax)] for _ in range(n+1)]
# 初期条件
dp[0][0] = 0
for i in range(n):
    for sum_v in range(vmax):
        # i番目の品物を選べるとき
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        # i番目の品物を選ばないとき
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 最適解を探す
ans = 0
for sum_v in range(vmax):
    if dp[n][sum_v] <= W:
        ans = sum_v
print(ans)
### BUGGY CODE ###

# とても時間がかかる

def main():
    n = int(input())
    count = 0
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            count += 1
    print(count)

def isprime(x: int):    
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:        
        yesno = 1
        for y in range(3, x//2, 2):
            # 偶数は最初に除外するので、奇数で割れるかだけ見ていく
            if x % y == 0:
                yesno = 0
                break
    return yesno

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    A = set()
    n_prime = 0
    while True:
        try:
            x = int(input())
            A.add(x)
        except:
            break

    for x in A:
        n_prime += is_prime(x)

    print(n_prime)


def is_prime(x):  
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:
        return pow(2, x - 1, x) == 1   

main()
### BUGGY CODE ###

# エラトステネスの篩
# https://qiita.com/takayg1/items/3769ab4cc62a231f4259

def eratosthenes_sieve(n):
    is_prime = [True]*(n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, n + 1):
        if is_prime[p]:
            for q in range(2*p, n + 1, p):
                is_prime[q] = False
    return is_prime

MAX_N=(10**6)
Primes = eratosthenes_sieve(MAX_N)

x = int(input())
while True:
    if Primes[x]:
        print(x)
        exit()

### FIXED CODE ###

x = int(input())

def is_prim(n):
    if n == 1: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

for i in range(x, 20**5+1):
    if is_prim(i):
        print(i)
        exit()
### BUGGY CODE ###

i = list(map(int, input().split()))
K = i[0]
N = i[1]

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

m = K

for i in range(N):
  for j in range(i,N):
    t = max(abs(s[i] - s[j]), K - abs(s[i] - s[j]))
    if t <= m:
      m = t
      
print(m)

### FIXED CODE ###

i = list(map(int, input().split()))
K = i[0]
N = i[1]

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

m = K

for i in range(N - 1):
  t = max(abs(s[i] - s[i + 1]), K - abs(s[i] - s[i + 1]))
  if t <= m:
     m = t

if max(abs(s[0] - s[N - 1]), K - abs(s[0] - s[N - 1])) <= m:
  m = max(abs(s[0] - s[N - 1]), K - abs(s[0] - s[N - 1]))

print(m)
### BUGGY CODE ###

import time

start = time.time()

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

s.sort()
s.reverse()

flag = True
for i in range(n):
    a = s[0:2 ** i]
    b = s[2 ** i:2 ** (i + 1)]
    for j in range(len(a)):
        if b[j] >= a[j]:
            flag = False
            break
if flag:
    print('Yes')
    exit()

s.reverse()

a = []
a.append(s[-1])
s.pop(-1)
for i in range(n):
    for j in range(len(a)):
        for k in range(len(s)):
            if a[j]>s[-1-k]:
                a.append(s[-1-k])
                s.pop(-1-k)
                break
    if len(a)!=2**(i+1):
        print('No')
        exit()
    if time.time() -start > 1.8:
        print('Yes')
        exit()
print('Yes')


### FIXED CODE ###

import time

start = time.time()

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

s.sort()
s.reverse()

flag = True
for i in range(n):
    a = s[0:2 ** i]
    b = s[2 ** i:2 ** (i + 1)]
    for j in range(len(a)):
        if b[j] >= a[j]:
            flag = False
            break
if flag:
    print('Yes')
    exit()

s.reverse()

a = []
a.append(s[-1])
s.pop(-1)
for i in range(n):
    for j in range(len(a)):
        for k in range(len(s)):
            if a[j]>s[-1-k]:
                a.append(s[-1-k])
                s.pop(-1-k)
                break
        if time.time() - start > 1.8:
            print('Yes')
            exit()
    if len(a)!=2**(i+1):
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

n, m = map(int, input().split())
money = []
for i in range(n):
  a, b = map(int, input().split())
  money += [a] * b

print(sum(sorted(money)[0:m]))

### FIXED CODE ###

n, m = map(int, input().split())
money = []
for i in range(n):
  a, b = map(int, input().split())
  money.append({"a":a, "b":b})

bsum = 0
money.sort(key=lambda x: x["a"])
for i in range(n):
  bsum0 = bsum
  bsum += money[i]["b"]
  if m <= bsum:
    num = i
    break

ans = 0
for j in range(num):
  ans += money[j]["a"] * money[j]["b"]
ans += (m-bsum0) * money[num]["a"]
print(ans)
### BUGGY CODE ###

def resolve():
    import math
    A, B, C, D = map(int, input().split())
    S = []
    E = C
    while len(S) == 0:
        if C%E == 0 and D%E == 0:
            S.append(E)
        E -= 1
    gcd = S[0]
    lcm = C*D//gcd
    A = A-1
    print((B-B//C-B//D+B//lcm)-(A-A//C-A//D+A//lcm))
resolve()

### FIXED CODE ###

def resolve():
    A, B, C, D = map(int, input().split())
    d = D
    c = C
    gcd = 0
    while gcd == 0:
        if d % c == 0:
            gcd = c
        else:
            e = d%c
            d = c
            c = e
    lcm = C*D//gcd
    A = A-1
    print((B-B//C-B//D+B//lcm)-(A-A//C-A//D+A//lcm))
resolve()
### BUGGY CODE ###

L, R = map(int, input().split())

count_limit = 0 # count limit is 2019
min_num = 2020
for i in range(L, R+1):
    for j in range(i+1, R+1):
        min_num = min(min_num, (i*j)%2019)

    # limit process
    count_limit = count_limit + 1
    if count_limit>2020:
        break

print(min_num)


### FIXED CODE ###

L, R = map(int, input().split())

count_limit = 0 # count limit is 2019
min_num = 2020
for i in range(L, R+1):

    count_limit_j = 0
    for j in range(i+1, R+1):
        min_num = min(min_num, (i*j)%2019)
        count_limit_j = count_limit_j + 1
        if count_limit_j>2020:
            break

    # limit process
    count_limit = count_limit + 1
    if count_limit>2020:
        break

print(min_num)
### BUGGY CODE ###

import itertools
N = input()
S = input()

com = list(set([c[0]+c[1]+c[2] for c in itertools.combinations(S,3)]))
#com = list(set([c[0]+c[1]+c[2] for c in itertools.combinations(N,3)]))
print(len(com))

### FIXED CODE ###

import itertools
N = input()
S = input()

#com = list(set([c[0]+c[1]+c[2] for c in itertools.combinations(S,3)]))
#com = list(set([c[0]+c[1]+c[2] for c in itertools.combinations(N,3)]))
#print(len(com))


# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
result = 0

for i in range(0,1000):
    s = str(i).zfill(3)
    #print(s[0] + '\d' + s[1] + '\d' + s[2])
    #pattern = '\d' + s[0] + '*\d' + s[1] + '*\d' + s[2] + '*\d'
    #import re
    #repattern = re.compile(pattern)
    #result = repattern.match(S)
    first_index = S.find(s[0])
    if first_index == -1:
        continue
    S_1 = S[first_index+1:]
    second_index = S_1.find(s[1])
    if second_index == -1:
        continue
    S_2 = S_1[second_index+1:]
    third_index = S_2.find(s[2])
    if third_index == -1:
        continue
    result += 1
print(result)
### BUGGY CODE ###

s=input()
ans=[0]*len(s)

for i in range(len(s)):
  cnt=0
  pin=s[i]
  pin2=s[i]
  j=i
  while True:
    if pin2=='L':
      j-=1
      pin2=s[j]
      pin3=j
    else:
      j+=1
      pin2=s[j]
      pin3=j
      
    if pin!=pin2:
      if cnt%2==0:
        if pin2=='L':
          ans[j-1]+=1
          break
        else:
          ans[j+1]+=1
          break
      else:
        ans[pin3]+=1
        break
    
    cnt+=1
    
ans=list(map(str,ans))

print(' '.join(ans))

### FIXED CODE ###

s=input()
ans=[1]*len(s)

for i in range(len(s)):
    if s[i]=='L':
      if s[i]==s[i-1]:
        ans[i-2]+=ans[i]
        ans[i]=0
        
    elif s[i]=='R':
      if s[i]==s[i+1]:
        ans[i+2]+=ans[i]
        ans[i]=0

for i in range(len(s)-1,-1,-1):
    if s[i]=='L':
      if s[i]==s[i-1]:
        ans[i-2]+=ans[i]
        ans[i]=0
        
    elif s[i]=='R':
      if s[i]==s[i+1]:
        ans[i+2]+=ans[i]
        ans[i]=0
        
        
ans=list(map(str,ans))

print(' '.join(ans))
### BUGGY CODE ###

N =int(input())
AB = [list(map(int,input().split())) for _ in range(N)]

ans = 0
for i in range(N):
  if AB[-1][0]%AB[-1][1]==0:
    push = 0
  else:
    push = (AB[-1][1] - (AB[-1][0]%AB[-1][1]))
  ans += push
  for j in range(len(AB)):
    AB[j][0] += push
  AB.pop()
print(ans)

### FIXED CODE ###

N =int(input())
a = [0] * N
b = [0] * N
for i in range(N):
    A, B = map(int, input().split())
    a[i], b[i] = A, B
    
ans = 0
for i in range(N-1,-1,-1):
  if (a[i]+ans)%b[i]==0:
    push = 0
  else:
    push = b[i] - (a[i]+ans)%b[i]
  ans += push
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
score = [int(K) for __ in range(N)]

for i in range(Q):
    for m in range(N):
        score[m] = score[m]-1
    score[A[i]-1] = score[A[i]-1]+1
for k in range(N):
    if score[k] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = map(int, input().split())
p = k-q
l = [p]*n
for i in range(q):
    a = int(input())
    l[a-1] += 1
for k in range(n):
    print("Yes" if l[k]>0 else "No")
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

dp = [-1 for i in range(len(h))]
dp[0] = 0

# print(dp)

for i in range(len(h)):
    # print(i)
    for j in range(1, k + 1):
        if i + j < len(dp):
            if dp[i + j] == -1:
                dp[i + j] = dp[i] + abs(h[i] - h[i + j])
            else:
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
            # print(dp)
        
print(dp[len(dp) - 1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
count = 0
if n==0:
    print(count)
    exit()
else:
    for i in range(n-1):
        count += i+1
print(count)

### FIXED CODE ###

n = int(input())
count = (n-1)*n//2
print(count)
### BUGGY CODE ###

s = input()
n = int(input())
query_li = (input().split() for i in range(n))

for query in query_li:
    if int(query[0]) == 1:
        s = s[::-1]
    else:
        if int(query[1]) == 1:
            s = query[2] + s
        else:
            s = s + query[2]

print(s)

### FIXED CODE ###

from collections import deque

s = deque(input().split())
n = int(input())
query_li = (input().split() for i in range(n))

flag = 1

for query in query_li:
    if int(query[0]) == 1:
        flag = flag * -1
    else:
        if int(query[1]) == 1:
            if flag == 1:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if flag == 1:
                s.append(query[2])
            else:
                s.appendleft(query[2])

s = ''.join(s)
if flag == -1:
    s = s[::-1]

print(s)
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=np.int64)

for i in range(N):
    w, v = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品を取る
        if w <= sum_w:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w] + v)
        # i番目の品を取らない
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    w, v = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品を取る
        if w <= sum_w:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w] + v)
        # i番目の品を取らない
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

MOD = 998244353
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(input())
a =[int(input()) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] #dp1[x]:Bの和=xとなるような塗り方の総数

dp1[0] = 1

for i in range(n):
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp1[j+a[i]] = (dp1[j]+dpp1[j+a[i]]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print((pow(3,n,MOD)-ans1*3) % MOD)
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in range(n):
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp2[j+a[i]] = (dp2[j]+dpp2[j+a[i]]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD)

### FIXED CODE ###

MOD = 998244353
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(input())
a =[int(input()) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] #dp1[x]:Bの和=xとなるような塗り方の総数

dp1[0] = 1

for i in  a:
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp1[j+i] = (dp1[j]+dpp1[j+i]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print((pow(3,n,MOD)-ans1*3) % MOD)
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in a:
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp2[j+i] = (dp2[j]+dpp2[j+i]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD)