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

# coding:utf-8
def main():
    a = int(input())
    list = []
    for i in range(a):
        list.append(int(input()))
    temp = list.copy()

    for i in range(a):
        list = temp.copy()
        list.pop(i)
        ans = max(list)
        print(ans)

if __name__ == '__main__' :
    main()

### FIXED CODE ###

# coding:utf-8
def main():
    a = int(input())
    lists= [int(input()) for _ in range(a)]

    temp = lists.copy()
    first = max(temp)
    temp.remove(first)
    second = max(temp)

    for i in range(a):
        if lists[i] == first:
            print(second)
        else:
            print(first)

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

from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos > 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())


### FIXED CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())
ab = [[int(i) for i in input().split()]for j in range(m)][1:]
 
ans = [0]*(m-1)+[int(n*(n-1)/2)]
l = np.array([i for i in range(1,n+1)])
s = {i:1 for i in range(1,n+1)}
def serch_l(num):
  if l[num]==num+1:
    return l[num]
  else:
    leader = serch_l(l[num]-1)
    l[num]=leader
    return leader
for k,i in enumerate(ab[::-1]):
  
  if l[i[0]-1] == l[i[1]-1]:
    ans[m-2-k]=ans[m-1-k]
  else:
    l_a,l_b = serch_l(i[0]-1),serch_l(i[1]-1)
    s_a,s_b = s[l_a],s[l_b]
    
    if s_a <= s_b:
      c = s_a*s_b
      s[l_b]+=s_a
      s[l_a]=0
      l[l==l_a]=l_b
      ans[m-2-k]=ans[m-1-k]-c
    else:
      c = s_a*s_b
      s[l_a]+=s_b
      s[l_b]=0
      l[l==l_b]=l_a
      ans[m-2-k]=ans[m-1-k]-c
  if ans[m-2-k]==0:
    break
for i in ans:
  print(i)

### FIXED CODE ###

n,m = map(int,input().split())
ab = [[int(i) for i in input().split()]for j in range(m)][1:]
ans = [0]*(m-1)+[int(n*(n-1)/2)]
l = [i for i in range(1,n+1)]
s = {i:1 for i in range(1,n+1)}
 
def serch_l(num):
  if l[num]==num+1:
    return l[num]
  else:
    leader = serch_l(l[num]-1)
    l[num]=leader
    return leader
    
for k,i in enumerate(ab[::-1]):
  k = m-1-k
  l_a,l_b = serch_l(i[0]-1),serch_l(i[1]-1)
  if l_a==l_b:
    ans[k-1]=ans[k]
  else:
    
    s_a,s_b = s[l_a],s[l_b]
    
    if s_a > s_b:
      (s_a,s_b) = (s_b,s_a)
      (l_a,l_b) = (l_b,l_a)
    c = s_a*s_b
    s[l_b]+=s_a
    s[l_a]=0
    l[l_a-1]=l_b
    ans[k-1]=ans[k]-c
for i in ans:
  print(i)
### BUGGY CODE ###

h,w,m=map(int,input().split())

hlis=[0 for i in range(h)]
wlis=[0 for i in range(w)]
lis=[[0 for _ in range(w)] for _ in range(h)]

for i in range(m):
  hi,wi=map(int,input().split())
  hlis[hi-1]+=1
  wlis[wi-1]+=1
  lis[hi-1][wi-1]+=1


hmax=max(hlis)
wmax=max(wlis)

ph=[]
pw=[]
for i in range(h):
  if hlis[i]==hmax:
    ph.append(i)
for i in range(w):
  if wlis[i]==wmax:
    pw.append(i)


cvac=0
for phi in ph:
  for pwj in pw:
    if lis[phi][pwj]==0:
      cvac+=1
      break
  if cvac==1:
    break

if cvac==1:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)

### FIXED CODE ###

import sys

h,w,m=map(int,input().split())


hlis=[0 for i in range(h)]
wlis=[0 for i in range(w)]
hw=[]

for i in range(m):
  hi,wi=map(int,input().split())
  hlis[hi-1]+=1
  wlis[wi-1]+=1
  hw.append([hi-1,wi-1])

hmax=max(hlis)
wmax=max(wlis)

ph=[]
pw=[]
for i in range(h):
  if hlis[i]==hmax:
    ph.append(i)
for i in range(w):
  if wlis[i]==wmax:
    pw.append(i)

if len(ph)*len(pw)>3*(10**5):
  print(hmax+wmax)
  sys.exit()

plis=[]
for phi in ph:
  for pwj in pw:
    plis.append(phi*(10**6)+pwj)

plis.sort()

hwlis=[]
for hi,wi in hw:
  hwlis.append(hi*(10**6)+wi)

hwlis.sort()
    
c=0
check=0

for pi in plis:
  while pi!=hwlis[c]:
    c+=1
    if c>=len(hwlis):
      check=1
      break
  if check==1:
    break

if check==1:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))

xy = [tuple(map(int, input().split())) for i in range(M)]

table = collections.defaultdict(set)

table2 = collections.defaultdict(int)
ans = 0
for i, x in enumerate(p):
    if i+1 == x:
        ans += 1
    else:
        table2[i + 1] = x
id = 0
for x, y in xy:
    a, b = -1, -1
    for z in table:
        if x in table[z]:
            a = z
            break
    for z in table:
        if y in table[z]:
            b = z
            break
    if a == b:
        if a == -1:
            table[id].add(x)
            table[id].add(y)
            id += 1
    elif a == -1 or b == -1:
        if a == -1:
            table[b].add(x)
        else:
            table[a].add(y)
    else:
        table[a] |= (table[b])
        del(table[b])

for x in table:
    for a in table[x]:
        if a in table2 and table2[a] in table[x]:
            ans += 1
print(ans)


### FIXED CODE ###

import collections
import sys


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(M)]
ans = 0
t = unionFind(N)

for x, y in xy:
    t.unite(x, y)

for i in range(N):
    if t.same(i+1, p[i]):
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
from heapq import heappush,heappop

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return tuple(map(int, ss_raw()))

INF = 1<<29

class MedianHeap:
    def __init__(self):
        self.lupper = []
        self.rlower =[]
        self.s=0
    def push(self,a):
        L = self.lupper
        R = self.rlower
        if len(L)== 0 or a<=-L[0]:
            heappush(L,-a)
            self.s+=-L[0]-a
            if len(L)-len(R)>=2:
                heappush(R,-heappop(L))
        else:
            heappush(R,a)
            self.s+=a+L[0]
            if len(R)>len(L):
                self.s+=-L[0]-R[0]
                heappush(L,-heappop(R))

def main():
    Q = int_raw()
    sb = 0
    lupper = []
    rlower = []
    s = 0
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            a,b = cmds[1:]
            sb+= b
            if len(lupper)== 0 or a<=-lupper[0]:
                heappush(lupper,-a)
                s+=-lupper[0]-a
                if len(lupper)-len(rlower)>=2:
                    heappush(rlower,-heappop(lupper))
            else:
                heappush(rlower,a)
                s+=a+lupper[0]
                if len(rlower)>len(lupper):
                    s+=-lupper[0]-rlower[0]
                    heappush(lupper,-heappop(rlower))  
        else:
            print (-lupper[0], s+sb)
    
main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from heapq import heappush,heappop

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))

def main():
    Q = int(input())
    sb = 0
    lupper = []
    rlower = []
    s = 0
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            _,a,b = cmds
            sb+= b
            if len(lupper)== 0 or a<=-lupper[0]:
                heappush(lupper,-a)
                s+=-lupper[0]-a
                if len(lupper)-len(rlower)>=2:
                    heappush(rlower,-heappop(lupper))
            else:
                heappush(rlower,a)
                s+=a+lupper[0]
                if len(rlower)>len(lupper):
                    s+=-lupper[0]-rlower[0]
                    heappush(lupper,-heappop(rlower))  
        else:
            print (-lupper[0], s+sb)
    
main()
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    p = max(0, j-A[j])
    q = min(n-1, j+A[j])
    C[p] += 1
    C[q+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    p = max(0, j-A[j])
    q = min(n-1, j+A[j])
    C[p] += 1
    C[q+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))
### BUGGY CODE ###

N,M = (int(x) for x in input().split())
cor = 0
mis = 0
numList = []
misList = {}

for _ in range(M):

    num,ans = input().split()

    if num not in numList:
        if num not in misList.keys():
            misList[num] = 0
            
        if ans == 'AC':
            cor += 1
            numList.append(num)
            mis += misList[num]
            misList.pop(num)
        else:
            misList[num] += 1

print(cor,mis)





### FIXED CODE ###

N,M = (int(x) for x in input().split())
cor = 0
mis = 0
numList = [0] * N
misList = [0] * N

for _ in range(M):
    num,ans = input().split()

    if ans == 'WA':
        misList[int(num)-1] += 1
    else:
        if numList[int(num)-1] == 0:
            mis += misList[int(num)-1]
            cor += 1
            numList[int(num)-1] = 1

print(cor,mis)
### BUGGY CODE ###

from functools import reduce
mod=10**9+7

def f(A):
 dem=reduce(lambda x,y:x*y,range(n,n-A,-1))
 num=reduce(lambda x,y:x*y,range(1,A+1))
 return dem*pow(num,mod-2,mod)%mod

stdin=open(0)
n,a,b=map(int,stdin.read().split())
ans=pow(2,n,mod)-f(a)-f(b)-1
ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
cnt = 0
for i in range(n):
  if m < 2: break
  cnt += 1
  n -= 1
  m -= 2
print(cnt+m//4)

### FIXED CODE ###

n,m = map(int, input().split())
ans = 0
if m >= 2 * n: 
    ans += n
    m -= 2 * n
    ans += m // 4
else: ans += m // 2
print(ans)
### BUGGY CODE ###

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

'''
4 4
1 3
2 2
1 1
2 4


'''
A.sort()

tmp = []

for t in target:
    for i in range(t[0]):
        tmp.append(t[1])
tmp.sort(reverse=True)


#print(A)
#print(tmp)
for i,a in enumerate(A):
    if i < len(tmp) and A[i] < tmp[i]:
        A[i] = tmp[i]
        #print(A)
    else:
        break

print(sum(A))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
target = [list(map(int, input().split())) for i in range(M)]
target = sorted(target, key = lambda x:x[1], reverse=True)
# print(target)

'''
4 4
1 3
2 2
1 1
2 4


'''


for t in target:
    A.extend([t[1]] * t[0])
    if len(A) > N * 2:
        break
A.sort(reverse=True)

print(sum(A[:N]))
### BUGGY CODE ###

import math
import numpy as np

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2:
        dic[t] = 1
        ans += t
    else:
        temp = (math.floor(k/t)**n)%moddo
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp
        ans = (ans+((temp*t)%moddo))%moddo

#for i in range(1,k+1):
#    ans += i*dic[i]
#    if ans >= moddo:
#        ans = ans%moddo
    
        
#print(dic)
#print(sum(dic.values()))
print(ans)

### FIXED CODE ###

import math

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

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

n = int(input())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
for xx in x:
    if y.index(xx) >= n//2:
        print(y[n//2 - 1])
    else:
        print(y[n//2])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
y_e = y[n//2]
y_o = y[n//2 - 1]
for xx in x:
    if xx >= y_e:
        print(y_o)
    else:
        print(y_e)
### BUGGY CODE ###

N = int(input())
S = input()

lis = [0 for _ in range(1000)]

usiro_lis = [[0 for _ in range(10)] for _ in range(N)]
for i in range(N)[::-1]:
  for j in range(0, i):
    usiro_lis[j][int(S[i])] = 1

for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(10):
      if usiro_lis[j][k] == 1:
      	lis[100*int(S[i])+10*int(S[j])+k] = 1
      
print(sum(lis))

### FIXED CODE ###

N = int(input())
S = input()
numbers=[str(i).zfill(3) for i in range(1000)]
 
count=0
for num in numbers:
  j=0
  for i in range(N):
    if num[j]==S[i]:
      j+=1
      if j==3:
        count+=1
        break
print(count)
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in raw_input().split()]
a = [0 for i in range(n)]
b = [0 for i in range(n)]

for i in range(n):
	a[p[i]-1] = i + 1
	b[p[i]-1] = i + 1
for i in range(1,n):
	d = min(a[i] - a[i-1],b[i-1] - b[i])
	if d <= 0:
		a[i] -= d - 1
		b[i] += d - 1
a = [str(i+1-min(a)) for i in a] 
b = [str(i+1-min(b)) for i in b]

print(" ".join(a))
print(" ".join(b))

### FIXED CODE ###

n = int(input())
p = [int(i) for i in raw_input().split()]
a = [0 for i in range(n)]
b = [0 for i in range(n)]
p.reverse()
for i in range(n):
	k = p.pop()
	a[k-1] = i + 1
	b[k-1] = i + 1
for i in range(1,n):
	d = min(a[i] - a[i-1],b[i-1] - b[i])
	if d <= 0:
		a[i] -= d - 1
		b[i] += d - 1
ma = min(a)
mb = min(b)
a = [str(i+1-ma) for i in a] 
b = [str(i+1-mb) for i in b]
print(" ".join(a))
print(" ".join(b))
### BUGGY CODE ###

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

import sys
import os
import math


n = int(input())
A = list(map(int, input().split()))
cnt = 0

def merge(A, left, mid, right):
    global cnt

    S = A[left:mid]
    T = A[mid:right]
    S.append(float('inf'))
    T.append(float('inf'))

    for i in range(right - left):
        cnt += 1
        if S[0] < T[0]:
            A[left + i] = S.pop(0)
        else:
            A[left + i] = T.pop(0)


def merge_sort(A, left, right):
    if left + 1 == right:
        # ???????????????
        return
    else:
        # ??????????????????
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

merge_sort(A, 0, len(A))
print(*A)
print(cnt)

### FIXED CODE ###

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

import sys
import os
import math


n = int(input())
A = list(map(int, input().split()))
cnt = 0

def merge(A, left, mid, right):
    global cnt

    S = A[left:mid]
    T = A[mid:right]
    S.append(float('inf'))
    T.append(float('inf'))

    s_i = 0
    t_i = 0
    for i in range(right - left):
        cnt += 1
        if S[s_i] < T[t_i]:
            A[left + i] = S[s_i]
            s_i += 1
        else:
            A[left + i] = T[t_i]
            t_i += 1


def merge_sort(A, left, right):
    if left + 1 == right:
        # ???????????????
        return
    else:
        # ??????????????????
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

merge_sort(A, 0, len(A))
print(*A)
print(cnt)
### BUGGY CODE ###

N =  int(input())
a = list(map(int,input().split( )))
ans = a[0]
if N % 2  == 1:
	for i in range(N-1):
		if (i+1) % 2 == 0:
			ans = str(a[i+1]) + ' ' + str(ans)
		else:
			ans = str(ans) + ' ' + str(a[i+1])
else:
	for i in range(N-1):
		if (i+1) % 2 == 1:
			ans = str(a[i+1]) + ' ' + str(ans)
		else:
			ans = str(ans) + ' ' + str(a[i+1])

print(ans)

### FIXED CODE ###

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

#if N % 2 == 0:
a_1 = a[0::2]
a_2 = a[1::2]
if N % 2 == 0:
	ans_list = a_2[::-1] + a_1
else:
	ans_list = a_1[::-1] + a_2

ans = ''
for i in range(N):
	if i == N-1:
		ans += str(ans_list[i])
	else:
		ans += str(ans_list[i]) + ' '
print(ans)
### BUGGY CODE ###

import sys

def frog(i,K,h,dp,INF):
   
    if dp[i]!=INF:
        return dp[i]
    else:
        cost=[]
        for k in range(1,K+1):
            if i-k-1>=0:
                cost.append(frog(i-k,K,h,dp,INF)+abs(h[i-1]-h[i-k-1]))
                continue
            break
        dp[i]=min(cost)
        return dp[i]
INF=100000000
sys.setrecursionlimit(INF)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N+1)]
dp[1]=0
dp[2]=abs(h[1]-h[0])
print(frog(N,K,h,dp,INF))


### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

from collections import deque
import sys

input = sys.stdin.readline

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
q = deque()
visited = [[W+H]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s == '#':
            visited[i][j] = 0
            q.append((i, j, 0))

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if 0 <= y+1 < H and visited[y+1][x] > lv+1:
        visited[y+1][x] = lv+1
        q.append((y+1, x, lv+1))

    if 0 <= y-1 < H and visited[y-1][x] > lv+1:
        visited[y-1][x] = lv+1
        q.append((y-1, x, lv+1))

    if 0 <= x+1 < W and visited[y][x+1] > lv+1:
        visited[y][x+1] = lv+1
        q.append((y, x+1, lv+1))

    if 0 <= x-1 < W and visited[y][x-1] > lv+1:
        visited[y][x-1] = lv+1
        q.append((y, x-1, lv+1))

print(res)

### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
### BUGGY CODE ###

import numpy as np
N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
wv = np.array(wv).reshape(N,2)
dp = np.zeros((110, 100100))
for i in range(N):
  for w in range(W+1):
    if w - wv[i,0] >= 0:
      dp[i+1,w] = max(dp[i+1,w], dp[i,(w-wv[i,0])]+wv[i,1])
    dp[i+1,w] = max(dp[i+1,w], dp[i, w])
print(int(dp[N,W]))

### FIXED CODE ###

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

n=int(input())
l=list(map(int,input().split()))
ans=1
f=1
i=0
for i in range(n):
  ans=ans*l[i]
if f==1 and ans<=10**18:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=1
f=1
i=0
for i in range(n):
  if ans<=10**18:
    ans=ans*l[i]
  else:
  	f=0
if f==1 and ans<=10**18:
  print(ans)
else:
  print(-1)
### BUGGY CODE ###

from bisect import bisect
from math import factorial
n = int(input())
R,B,G = [],[],[]
m,M,mid = [],[],[]
ans = factorial(n)
for i,j in enumerate(input()):
	if j=="R":
		R += [i]
	elif j=="B":
		B += [i]
	else:
		G += [i]
for r,b,g in zip(R,B,G):
	f,s,t = sorted([r,b,g])
	m += [f]
	M += [t]
	mid += [s]
for i,j in enumerate(mid):
	i = bisect(m,j) - i
	if i > 1:
		ans *= i
for i,j in enumerate(mid[::-1]):
	i = n - i - bisect(M,j)
	if i > 1:
		ans *= i
print(ans)

### FIXED CODE ###

import math
n=int(input())
c={"R":0,"G":0,"B":0}
a=1
mod=998244353
for i in input():
	s=sorted((c["R"],c["G"],c["B"]))
	c[i]+=1
	if c[i]>s[2]:
		pass
	elif c[i]>s[1]:
		a*=s[2]-s[1]
	else:
		a*=s[1]-s[0]
	a%=mod
print(math.factorial(n)*a%mod)
### BUGGY CODE ###

import bisect

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

YZ = Y*Z
BC = []
for b in B:
  for c in C:
    BC.append(b+c)

BC.sort()
# 2つのリストから1つずつ要素を取り出したときに和がx以上となる組合せ
def count_large_2(L1, L2, x):
  # L1.sort()
  # L2.sort(reverse=True)
  N1, N2 = len(L1), len(L2)
  i = j = 0
  c = 0
  while i<N1 and j<N2:
    if L1[i]+L2[j] >= x:
      c += 1
      j += 1
      if j >= N2:
        c += (N1-i-1) * N2
    else:
      i += 1
      if i>=N1:
        continue
      c += j
  return c


def check(S):
  c = count_large_2(BC, A, S)  
  return c >= K



Sl = 0
Sr = A[0]+B[0]+C[0]+1

while Sr - Sl > 1:
  mid = (Sl + Sr) // 2
  if check(mid):
    Sl = mid
  else:
    Sr = mid


Ans = []
for a in A:
  for b in B:
    if a + b + C[0] < Sr:
      break
    for c in C:
      if a + b + c >= Sr:
        Ans.append(a+b+c)
      else:
        break

Ans.sort(reverse=True)
Ans = Ans + [Sl]*(K-len(Ans))
for ans in Ans:
  print(ans)

### FIXED CODE ###

import bisect

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

YZ = Y*Z
BC = []
for b in B:
  for c in C:
    BC.append(b+c)

BC.sort()
def check(S):
  count = 0
  left = X*Y*Z
  for a in A:
    count += YZ - bisect.bisect_left(BC, S-a)
    left -= YZ
    if count >= K or count+left < K:
      break
  
  return count >= K



Sl = 0
Sr = A[0]+B[0]+C[0]+1

while Sr - Sl > 1:
  mid = (Sl + Sr) // 2
  if check(mid):
    Sl = mid
  else:
    Sr = mid

Ans = []
for a in A:
  for b in B:
    if a + b + C[0] < Sr:
      break
    for c in C:
      if a + b + c >= Sr:
        Ans.append(a+b+c)
      else:
        break

Ans.sort(reverse=True)
Ans = Ans + [Sl]*(K-len(Ans))
for ans in Ans:
  print(ans)