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

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

A = list(map(int, input().split()))
S = [list(map(int,input().split())) for i in range(M)]

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

X = [0]*(len(A))
idx = 0

for i in range(M):
    for _ in range(S[i][0]):
        if idx < len(A):
            X[idx]=S[i][1]
            idx += 1

for i in range(idx):
    A[i] = max(A[i], X[i])

print(sum(A))

### FIXED CODE ###

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

A = list(map(int, input().split()))
S = [list(map(int,input().split())) for i in range(M)]

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

idx = 0

for i in range(M):
    for j in range(idx, min(N, idx + S[i][0])):
        if A[j] < S[i][1]:
            A[j] = S[i][1]
            idx += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    print(min(x_set))
  else:
    print(-1)

### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

from collections import defaultdict
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = defaultdict(int)
counter[mods[-1]] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10
  
result = 0
for j in counter.values():
  if j >= 2:
    result += j*(j-1)//2
print(result)

### FIXED CODE ###

S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10
  d %= 2019

print(result)
### 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 ###

h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)

### FIXED CODE ###

h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
gg = n // g
for i in range(rr+1):
  for j in range(gg+1):
    if n >= i*r + j*g and (n - (i*r + j*g)) %  b == 0:
        count += 1
print(count)


### FIXED CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
for i in range(rr+1):
  for j in range((n-i*r)//g+1):
    tmp = n - (i*r + j*g)
    if tmp >= 0 and tmp %  b == 0:
        count += 1
print(count)
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

if N < M:
    N, M = M, N
    S, T = T, S


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    idxs = [i for i, x in enumerate(arr1) if x == t]
    # print(idxs)

    for idx in idxs:
        ans += solve(i + idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

MOD = 10 ** 9 + 7

dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
    A[b].add(a)
S = [1]
while S:
    a_1 = S[0]
    for a_2 in A[a_1]:
        A[a_2] -= {a_1}
        S += a_2,
    S.pop(0)
C = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    C[p] += x
for i in range(1, n+1):
    c = C[i]
    for a in A[i]:
        C[a] += c
print(*C[1:])

### FIXED CODE ###

n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
C = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    C[p] += x
for i in range(1, n+1):
    c = C[i]
    for a in A[i]:
        C[a] += c
print(*C[1:])
### BUGGY CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
dp = [[""] * (m + 5) for _ in range(n + 5)]
for i in range(n):
    for j in range(m):
        if len(dp[i + 1][j]) < len(dp[i][j]):
            dp[i + 1][j] = dp[i][j]
        if len(dp[i][j + 1]) < len(dp[i][j]):
            dp[i][j + 1] = dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + s[i]
# print(dp)
ans = ""
for i in range(n + 1):
    for j in range(m + 1):
        if len(ans) < len(dp[i][j]):
            ans = dp[i][j]
print(ans)

### FIXED CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * 3100 for _ in range(3100)]
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

# print(dp)
ans = ""
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
l = [i for i in range(1, n+1)]
alpha_dict = {}
for i,c in enumerate(range(ord('A'),ord('Z')+1)):
  alpha_dict[i+1] = chr(c)

ans = set()
for v in itertools.product(range(1, n+1), repeat=n):
  m = min(v)
  used = []
  dic = {i:0 for i in range(n+1)}
  tmp = ""
  for u in v:
    if dic[u] == 0:
      dic[u] = len(used)+1
      used += [u]
      tmp += str(alpha_dict[dic[u]]).lower()
    else:
      tmp += str(alpha_dict[dic[u]]).lower()
  ans.add(tmp)

ans = sorted(list(ans))
for v in ans:
  print(v)



### FIXED CODE ###

n = int(input())
alpha_dict = {}
for i,c in enumerate(range(ord('A'),ord('Z')+1)):
  alpha_dict[i] = str(chr(c)).lower()


ans = []
def dfs(s, mx, ans):
  if len(s) == n:
    ans += [s]
    return 
  else:
    for i in range(mx+2):
      dfs(s+alpha_dict[i], max(i, mx), ans)

dfs("", -1, ans)
ans = sorted(ans)
for a in ans:
  print(a)
### BUGGY CODE ###

s = input()
t = input()
n = len(s)
m = len(t)

dp = [[0]*(m+1) for _ in range((n+1))]

for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
      
ans = ''
i = len(s)
j = len(t)
while i>0 and j>0:
  if dp[i][j] == dp[i-1][j]:
    i-=1    
  elif dp[i][j] == dp[i][j-1]:
    j-=1
  else:
    i-=1
    j-=1
    ans = s[i]+ans
    
print(ans)    

### FIXED CODE ###

s = input()
t = input()
n = len(s)
m = len(t)

dp = [[0]*(m+1) for _ in range((n+1))]

for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
      
ans = ''
i = len(s)
j = len(t)
while i>0 and j>0:
  if dp[i][j] == dp[i-1][j]:
    i-=1    
  elif dp[i][j] == dp[i][j-1]:
    j-=1
  else:
    i-=1
    j-=1
    ans = s[i]+ans
    
print(ans)
### BUGGY CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]
ans = 0
dic = {}
for s in S:
    if s in dic:
        ans += dic[s]
        dic[s] += 1
    else:
        dic[s] = 1

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

x = int(input())

if x==2 or x==3:
    print(x)
    exit()

lst = [i for i in range(x,x*2+2)]

max = int(x**0.5)
for i in range(2,max+1):
    for j in lst:
        if j%i==0:
            lst.remove(j)

print(lst[0])


### FIXED CODE ###

import math
x = int(input())

# if x==2 or x==3:
#     print(x)
#     exit()
#
# lst = [i for i in range(x,x*2+2)]
#
# max = int(x**0.5)
# for i in range(2,max+1):
#     for j in lst:
#         if j%i==0:
#             lst.remove(j)
#
# print(lst[0])


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

for i in range(x,x*2+2):
    if is_prime(i):
        print(i)
        exit()
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 1
for x in A:
    ans *= x
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
if 0 in A:
    print(0)
    exit()
ans = 1
for x in A:
    ans *= x
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    ac_list = []
    for (pi, si) in zip(p, S):
        if si=="AC":
            ac_list.append(pi)
    ac_list = list(set(ac_list))
    num_ans = len(ac_list)

    num_penalty = 0
    for (pi, si) in zip(p, S):
        # check ac
        if pi in ac_list:
            if si == "WA":
                num_penalty += 1
            else:
                tmp = ac_list.remove(pi)
        if len(ac_list) == 0:
            break

    print(num_ans, num_penalty)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int()] * (M)  # type: "List[int]"
    S = [str()] * (M)  # type: "List[str]"
    for i in range(M):
        p[i] = int(next(tokens))
        S[i] = next(tokens)
    solve(N, M, p, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    wa_flag = [0] * N
    num_penalty = 0
    for i in range(M):
        if S[i] == "WA":
            if wa_flag[p[i]-1] != -1:
                wa_flag[p[i]-1] += 1
        else:
            if wa_flag[p[i]-1] != -1:
                num_penalty += wa_flag[p[i]-1]
                wa_flag[p[i]-1] = -1
    num_ac = wa_flag.count(-1)
    print(num_ac, num_penalty)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M = map(int, input().split())
    p = [None] * M
    S = [None] * M
    for i in range(M):
        pi, si = input().split()
        p[i] = int(pi)
        S[i] = str(si)
    solve(N, M, p, S)

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

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

X = 1
for i in range(N):
    X = X * a[i]

if X > 1000000000000000000:
    print("-1")
else:
    print(X)


### FIXED CODE ###

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

X = 1

for i in range(N):
    if a[i] == 0:
        X = 0

if X == 1:
    for i in range(N):
        X = X * a[i]
        if X > 1000000000000000000:
            X = -1
            break

print(X)
### BUGGY CODE ###

def main():
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for _ in range(H)]
    B = [[int(i) for i in input().split()] for _ in range(H)]
    M = (H + W) * 80 + 1

    u = [[False] * M for _ in range(W)]
    v = [[False] * M for _ in range(W)]
    v[0][0] = True
    for h in range(H):
        v, u = u, v
        for w in range(W):
            a, b = A[h][w], B[h][w]
            d = a - b if a > b else b - a
            for i in range(M):
                t = False
                if 0 <= i + d < M:
                    t = t or u[w][i + d] or (w > 0 and v[w - 1][i + d])
                if 0 <= i - d < M:
                    t = t or u[w][i - d] or (w > 0 and v[w - 1][i - d])
                if 0 <= d - i < M:
                    t = t or u[w][d - i] or (w > 0 and v[w - 1][d - i])
                v[w][i] = t
    vv = v[-1]
    for i in range(M):
        if vv[i]:
            print(i)
            return
    raise

main()


### FIXED CODE ###

def main():
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for _ in range(H)]
    B = [[int(i) for i in input().split()] for _ in range(H)]
    M = (H + W) * 80 + 1

    u = [[False] * M for _ in range(W)]
    v = [[False] * M for _ in range(W)]
    F = [False] * M
    v[0][0] = True
    for h in range(H):
        v, u = u, v
        vl = F
        for w in range(W):
            a, b = A[h][w], B[h][w]
            d = a - b if a > b else b - a
            uu = u[w]
            vv = v[w]
            for i in range(M):
                di = i - d if i > d else d - i
                vv[i] = ((i + d < M and (uu[i + d] or vl[i + d])) or
                           (uu[di] or vl[di]))
            vl = vv
    va = v[-1]
    for i in range(M):
        if va[i]:
            print(i)
            return
    raise

main()
### BUGGY CODE ###

import itertools
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    cnt=0
    for i in itertools.combinations(range(101),n):
        if sum(i)==s:
            cnt+=1
        if i[0]>=s:break
    print cnt

### FIXED CODE ###

dp=[[0]*1001 for i in range(11)]
dp[0][0]=1
for i in range(101):
    for j in range(10)[::-1]:
        for k in range(1001-i):
            dp[j+1][k+i]+=dp[j][k]
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    print dp[n][s]
### BUGGY CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
    print(-1)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


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

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

hako = [0] * (N+1)

for i in range(1,N+1)[::-1]:
    if i > N / 2:
        if a[i-1] == 1:
            hako[i] = a[i-1]
    else:
        count = 0
        for j in range(i+1,N+1):
            if j%i == 0:
                count += a[j-1]

        if count % 2 == a[i-1]:
            hako[i] = 0
        else:
            hako[i] = 1

print(sum(hako))

if sum(hako):
    ans = []
    for i, bin in enumerate(hako):
        if bin:
            ans.append(i)
    print(*ans)

### FIXED CODE ###

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

hako = [0] * (N+1)

for i in range(1,N+1)[::-1]:
    if i > N / 2:
        if a[i-1] == 1:
            hako[i] = a[i-1]
    else:
        count = 0
        for j in range(i,N+1,i):
            if j%i == 0:
                count += hako[j]

        if count % 2 == a[i-1]:
            hako[i] = 0
        else:
            hako[i] = 1

print(sum(hako))

if sum(hako):
    ans = []
    for i, bin in enumerate(hako):
        if bin:
            ans.append(i)
    print(*ans)
### BUGGY CODE ###

import bisect


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

a = sorted(a)
end = bisect.bisect_right(a, k)
a = a[0:end]
n = len(a)

#rightの部分和の集合を予め求めておく
right_subset_sum = [None] * (n+1)
right_subset_sum[-1] = set([0])
for i in range(n)[::-1]:
    a_i = a[i]
    tmp_set = set([])
    if a_i <= k:
        tmp_set.add(a_i)
    for j in right_subset_sum[i+1]:
        if j + a_i <= k:
            tmp_set.add(j + a_i)
    right_subset_sum[i] = right_subset_sum[i+1] | tmp_set

ans = 0
left_subset_sum = set([0])

for i in range(n):
    a_i= a[i]
    li = sorted(list(right_subset_sum[i+1]))
    for num in left_subset_sum:
        left = k - a_i - num
        right = k - num
        if bisect.bisect_left(li, right) - bisect.bisect_left(li, left) > 0:
            break
    else:
        ans += 1
    #leftの集合にa_iを含めた部分和を追加する
    tmp_set = set([])
    if a_i <= k:
        tmp_set.add(a_i)
    for j in left_subset_sum:
        if j + a_i <= k:
            tmp_set.add(j + a_i)
    left_subset_sum = left_subset_sum | tmp_set
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


def solve(mid):
    """のぞいてもいいカードならTrueを返す"""
    dp = 1
    mask = (1 << k) - 1
    if k <= a[mid]:
        return False
    for i, weight in enumerate(a):
        if i == mid:
            continue
        dp |= dp << min(weight, k + 10)
        dp &= mask
    return dp >> (k - a[mid]) == 0
     

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

a.sort()
ok = 0
ng = n
if not solve(ok):
    print(0)
    exit()

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list((x,i) for i,x in enumerate(a))
b.sort(reverse=True)
dp = [[0]*(n+1-i) for i in range(n+1)]
for i in range(n):
    x,idx = b[i]
    for j in range(i+1):
        k = i-j
        if dp[j+1][k] < dp[j][k] + x*(idx-j):
            dp[j+1][k] = dp[j][k] + x*(idx-j)
        if dp[j][k+1] < dp[j][k] + x*((n-1-k)-idx):
            dp[j][k+1] = dp[j][k] + x*((n-1-k)-idx)
ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list((x,i) for i,x in enumerate(a))
b.sort(reverse=True)
dp = [[0]*(n+1-i) for i in range(n+1)]
for i in range(n):
    x,idx = b[i]
    for j in range(i+1):
        k = i-j
        if dp[j+1][k] < dp[j][k] + x*(idx-j):
            dp[j+1][k] = dp[j][k] + x*(idx-j)
        if dp[j][k+1] < dp[j][k] + x*((n-1-k)-idx):
            dp[j][k+1] = dp[j][k] + x*((n-1-k)-idx)
ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)