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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[False]*K
        dp[0]=True
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    


main()


### FIXED CODE ###

def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
 
    

main()
### BUGGY CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))


### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
### BUGGY CODE ###

a,b=map(int,input().split())
K=1
for i in range(a,b+1):
    K*=i
if K>0:
    print('Positive')
elif K<0:
    print('Negative')
else:
    print('Zero')

### FIXED CODE ###

a,b=map(int,input().split())
K=1
if a>0:
    print('Positive')
elif a<=0 and b>=0:
    print('Zero')
elif (b-a)%2==0:
    print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    adj = [[] for _ in range(H*W)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    ans = 0
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                tmp = 1
                for k in range(4):
                    y = i + dy[k]
                    x = j + dx[k]
                    while 0 <= y < H and 0 <= x < W:
                        if S[y][x] == '.':
                            tmp += 1
                            y += dy[k]
                            x += dx[k]
                        else:
                            break
                ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    # L[i][j]: このマスが光る時に左方向に照らされるマスの個数
    L = [[0]*W for _ in range(H)]
    R = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    # U[i][j]: このマスが光る時に上方向に照らされるマスの個数
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                if S[i-1][j] == '.': 
                    U[i][j] = U[i-1][j] + 1
            if S[H-i-1][j] == '.':
                if S[H-i][j] == '.': 
                    D[H-i-1][j] = D[H-i][j] + 1
    ans = 0
    
    for i in range(H):
        for j in range(W):
            tmp = 1
            tmp += L[i][j] + R[i][j] + U[i][j] + D[i][j]
            ans = max(tmp,ans)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
import os
import math

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

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

A.sort()
print(A[K-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import os
import math

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

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

A.sort()

i = 0
cnt = 0
for a in A:
    v = a[0]
    num = a[1]
    cnt += num

    if cnt >= K:
        print(v)
        break
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

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

b = [0] * n

for i in range(n-1):
    b[(a[i]-1)] += 1
    
for i in range(n):
    print(b[i])
### BUGGY CODE ###

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(first_word) == get_counter(second_word)
flag=0
n=int(input())
list1=[]

for i in range(n):
    list1.append(input())
for i in range(n):
    for j in range(n):
        if i<j:
            if verify_anagrams(list1[i], list1[j]):
                flag=flag+1
print(flag)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
d = defaultdict(int)
 
for i in range(N):
    s = str(sorted(input()))
    d[s] += 1
ans = 0
 
for key in d.keys():
    ans += d[key]*(d[key]-1)//2
print(ans)
### BUGGY CODE ###

a,b,x=map(int,input().strip().split(" "))
count=0

for i in range(a,b+1):
    if(i%x==0):
        count+=1

print(count)


### FIXED CODE ###

a, b, x = [int(x) for x in input().split()]
print(b // x - a // x + (a % x == 0))
### BUGGY CODE ###

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

for i in range(K+1, N+1):
  s = x[i-1]
  for j in range(1, K):
    s *= x[i-1-j]
  u = s/(x[i-1])*(x[i-K-1])
  u=int(u)

  if u<s:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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


for i in range(K+1, N+1):
  

  if x[i-K-1]<x[i-1]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

s=str(input())
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
ans=s
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans=l[i][2]+ans
			else:
				ans+=l[i][2]
		else:
			if l[i][1]=='2':
				ans=l[i][2]+ans
			else:
				ans+=l[i][2]
if c%2==1:
	print(ans[::-1])
else:
	print(ans)





### FIXED CODE ###

from collections import deque
ans=deque()
ans.append(str(input()))
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
		else:
			if l[i][1]=='2':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
A="".join(map(str,list(ans)))
if c%2==1:
	print(A[::-1])
else:
	print(A)
### BUGGY CODE ###

S = [c for c in input()]
ans = 0
while True:
    flag = False
    for i in range(len(S)-1):
        if S[i] == "B" and S[i+1] == "W":
            ans += 1
            flag = True
            S[i] = "W"
            S[i+1] = "B"
    if not flag:
        break
print(ans)


### FIXED CODE ###

S = [c for c in input()]
ans = 0
black = 0
for i in range(len(S)):
    if S[i] == "W":
        ans += black
    else:
        black += 1
print(ans)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
xs = []
for a in A:
    heapq.heappush(xs, a)

for _ in range(M):
    B, C = map(int, input().split())
    count = 0
    while xs[0] < C and count < B:
        heapq.heappop(xs)
        count += 1
        heapq.heappush(xs, C)
print(sum(xs))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((B, C))
BC.sort(key=lambda bc: (bc[1], bc[0]), reverse=True)

ai = 0
bci = bcj = 0
while ai < N and bci < M:
    if A[ai] < BC[bci][1]:
        A[ai] = BC[bci][1]
        ai += 1
        bcj += 1
        if BC[bci][0] <= bcj:
            bci += 1
            bcj = 0
    else:
        ai += 1
print(sum(A))
### BUGGY CODE ###

import numpy as np

N = int(input())

A = np.zeros(N)



for i in range(N):
   for j in range(N):
       for k in range(N):
           x = i + 1
           y = j + 1
           z = k + 1
           n = x**2 + y**2 + z**2 + x*y + y*z + z*x
           if N < n :
               continue
           else:
               A[n-1] += 1



for a in A:
    print(int(a))

### FIXED CODE ###

import numpy as np

N = int(input())
rN = int(np.sqrt(N))

A = np.zeros(N)



for i in range(rN):
   for j in range(rN):
       for k in range(rN):
           x = i + 1
           y = j + 1
           z = k + 1
           n = x**2 + y**2 + z**2 + x*y + y*z + z*x
           if N < n :
               break
           else:
               A[n-1] += 1



for a in A:
    print(int(a))
### BUGGY CODE ###

import bisect

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

for i in range(M):
    B,C = map(int, input().split())
    insert_index = bisect.bisect_left(A,C)
    if insert_index == 0 and C > A[0]:
        A[0] = C
        continue
    elif insert_index == 0:
        continue

    if insert_index >= B:
        tmp = A[B:insert_index]+[C]*B+A[insert_index:]
    else:
        tmp = [C]*insert_index+A[insert_index:]
    A = tmp

print(sum(A))

### FIXED CODE ###

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

BC = []

for i in range(M):
    BC.append(list(map(int, input().split())))

BC.sort(key=lambda x: x[1],reverse=True)

bc = 0
a = 0
ans = 0
for i in range(N):
    if (bc < M) and (BC[bc][1] >= A[a]):
        ans += BC[bc][1]
        BC[bc][0] -= 1
        if BC[bc][0] == 0:
            bc += 1
    else:
        ans += A[a]
        a += 1

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

s = input()
MOD = 10**9 + 7

dp = [[0 for i in range(13)] for j in range(2)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1, len(s)):
    for j in range(13):
        dp[i%2][j] = 0

    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i%2][(10*j+k)%13] = (dp[i%2][(10*j+k)%13] + dp[(i-1)%2][j]) % MOD
    else:
        k = int(s[i])
        for j in range(13):
            dp[i%2][(10*j+k)%13] = (dp[i%2][(10*j+k)%13] + dp[(i-1)%2][j]) % MOD

    # print(dp[(i-1)%2])
    # print(dp[i%2])
    # print()


print(dp[(len(s)-1)%2][5])


### FIXED CODE ###

s = input()
MOD = 10**9 + 7

dp = [[0 for i in range(13)] for j in range(2)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1, len(s)):
    for j in range(13):
        dp[i%2][j] = 0

    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i%2][(10*j+k)%13] = (dp[i%2][(10*j+k)%13] + dp[(i-1)%2][j]) % MOD
    else:
        k = int(s[i])
        for j in range(13):
            dp[i%2][(10*j+k)%13] = (dp[i%2][(10*j+k)%13] + dp[(i-1)%2][j]) % MOD

    # print(dp[(i-1)%2])
    # print(dp[i%2])
    # print()


print(dp[(len(s)-1)%2][5])
### BUGGY CODE ###

n,m=map(int, input().split())
ans=[0]*n
for _ in range(m):
    l,r=map(int, input().split())
    for i in range(l, r+1):
        if l<=i<=r:
            ans[i-1]+=1
print(ans.count(m))

### FIXED CODE ###

n,m=map(int, input().split())
maxl=0
minr=n
for _ in range(m):
    l,r=map(int, input().split())
    maxl = max(maxl, l)
    minr = min(minr, r)
print(minr-maxl+1 if maxl<=minr else 0)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
ans = -float("inf")
for x in range(n):
    num = math.floor(a*(x+1)/b) - a*(math.floor((x+1)/b))
    if num > ans:
        ans = num
print(ans)

### FIXED CODE ###

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

if n < b-1:
    print(a*(n%b)//b)
else:
    print(a*((b-1)%b)//b)
### BUGGY CODE ###

s,t=input(),input()
m,n=len(s),len(t)
c=[[0]*(n+1) for _ in range(m+1)]
fro=[['']*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1]==t[j-1]:
            c[i][j]=c[i-1][j-1]+1
            fro[i][j]='upper_left'
        elif c[i-1][j]>=c[i][j-1]:
            c[i][j]=c[i-1][j]
            fro[i][j]='above'
        else:
            c[i][j]=c[i][j-1]
            fro[i][j]='left'
x=''
a,b=m,n
while a>0 and b>0:
    if fro[a][b]=='upper_left':
        x+=s[a-1]
        a-=1;b-=1
    elif fro[a][b]=='above':
        a-=1
    else:
        b-=1
print(x[::-1])

### FIXED CODE ###

s,t=input(),input()
m,n=len(s),len(t)
c=[[0]*(n+1) for _ in range(m+1)]
fro=[['']*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1]==t[j-1]:
            c[i][j]=c[i-1][j-1]+1
            fro[i][j]='upper_left'
        elif c[i-1][j]>=c[i][j-1]:
            c[i][j]=c[i-1][j]
            fro[i][j]='above'
        else:
            c[i][j]=c[i][j-1]
            fro[i][j]='left'
x=''
a,b=m,n
while a>0 and b>0:
    if fro[a][b]=='upper_left':
        x+=s[a-1]
        a-=1;b-=1
    elif fro[a][b]=='above':
        a-=1
    else:
        b-=1
print(x[::-1])
### BUGGY CODE ###

import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1) // 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)
#    print(As)

print(sum(As))

### FIXED CODE ###

import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1)

    if(discount == 0):
        break

    discount //= 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)
#    print(As)

print(sum(As))
### BUGGY CODE ###

n =int(input())

a = [x for x in input().split()]

ls = []

ls.append(a[0])
if n%2==0:
    for i in range(1,n):
        if i%2==0:
            ls.append(a[i])
        else:
            ls.insert(0,a[i])
else:
    for i in range(1,n):
        if i%2==1:
            ls.append(a[i])
        else:
            ls.insert(0,a[i])

print(" ".join(ls))

### FIXED CODE ###

n =int(input())
a = list(map(str,input().split()))
lss = []
lse = []
if n%2==0:
    for i in range(n//2):
        lss.append(a[2*i])
    for i in range(n//2):
        lse.append(a[n-(2*i+1)])

else:
    for i in range(n//2):
        lss.append(a[2*i+1])
    for i in range(n//2+1):
        lse.append(a[n-2*i-1])


ls = lse+lss

print(" ".join(ls))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_a = set()
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            divnum_of_a.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    use_divnum = use_divnum or divnum_of_a
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

# coding: utf-8
# Your code here!

table=[0,2,5,5,4,5,6,3,7,6]

n,mmm = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = [0]*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(n+10)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(n+1):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))
#    print(ans)

print(ans[n])

        

### FIXED CODE ###

# coding: utf-8
# Your code here!

table=[0,2,5,5,4,5,6,3,7,6]

n,mmm = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = ['0']*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(100)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(90):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))
#print(ans)
if n < 90:
    print(ans[n])
else:
    mn = maxnum[minbar]
    ans2=0
    for i in range(90):
        if n>=i and (n-i)%minbar == 0:
            q=(n-i)//minbar
            if ans[i]=='0' : continue
            X = ''.join([j for j in ans[i] if j > mn])
            Y = ''.join([j for j in ans[i] if j <= mn])
            tmp = int(X+str(mn)*q+Y)
#            print(tmp,X,Y,ans[i],i)
            ans2 = str(max(int(ans2),tmp))
    print(ans2)
### BUGGY CODE ###

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp2 = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
dp2[0][0] = 1
dp2[0][a[0]] = 1 
allc = 3
flag = 0
if(suma%2 == 0):
	flag = 1
for i in range(1,N/2+1):
	allc = allc*9
	if(i*2 >= N):
		allc = allc/3
		k = a[i*2-1]
		for j in range(suma+1):
			if(j < k):
				dp[i][j] = dp[i-1][j]*2
				dp2[i][j] = dp2[i-1][j]
			else:
				dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
	else:
		k = a[i*2-1]
		l = a[i*2]
		if(k<l):
			k,l = l,k
		for j in range(sum(a[:i*2+1])+1):
			if(j < l):
				dp[i][j] = dp[i-1][j]*4
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j]
			elif(j < k):
				dp[i][j] = dp[i-1][j]*4 + dp[i-1][j-l]*2
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-l]
			elif(j < k+l):
				dp[i][j] = dp[i-1][j]*4 + dp[i-1][j-l]*2 + dp[i-1][j-k]*2
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-l] + dp2[i-1][j-k]
			else:
				dp[i][j] = dp[i-1][j]*4+ dp[i-1][j-l]*2 + dp[i-1][j-k]*2 + dp[i-1][j-k-l]
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j]+ dp2[i-1][j-l] + dp2[i-1][j-k] + dp2[i-1][j-k-l]
allc = allc - sum(dp[N/2][suma-suma/2:])*3
if(flag == 1):			
	allc += dp2[N/2][suma/2]*3
print(allc%DIV)

### FIXED CODE ###

import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))
### BUGGY CODE ###

N = int(input())

Q = [i for i in range(1, N+1)]
P = sum(Q) - Q[-1]
print(P)


### FIXED CODE ###

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

import sys
sys.setrecursionlimit(1000000)


n,m=map(int,input().split())

p=[[] for _ in range(n)]

for _ in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)

f=[-1 for _ in range(n)]

def calc(x):
    if len(p[x])==0:
        f[x]=0
        return 0
    f[x]=max([calc(i) for i in p[x]])+1
    return f[x]

m=0
for i in range(n):
    if f[i]!=-1:
        continue
    m=max(m,calc(i))
print(m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


n,m=map(int,input().split())

p=[[] for _ in range(n)]

for _ in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)

f=[-1 for _ in range(n)]

def calc(x):
    if f[x]!=-1:
        return f[x]
    if len(p[x])==0:
        f[x]=0
        return 0
    f[x]=max([calc(i) for i in p[x]])+1
    return f[x]

m=0
for i in range(n):
    if f[i]!=-1:
        continue
    m=max(m,calc(i))
print(m)