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

import numpy as np

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

A.sort(reverse=True)
row = [A[0], A[1]]
min_list =[A[1], A[1]]
ans = A[0]
for i in range(2, N):
    index = np.argmax(min_list)
    ans += min_list[index]
    if index == len(min_list)-1:
        l, r = row[index], row[0]
    else:
        l, r = row[index], row[index+1]
    row.insert(index+1, A[i])
    min_list[index] = A[i]
    min_list.insert(index+1, A[i])
print(ans)



### FIXED CODE ###

# import numpy as np
from collections import deque

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

A.sort(reverse=True)
# row = [A[0], A[1]]
min_list = deque([A[1], A[1]])
ans = A[0]
for i in range(2, N):
    # index = np.argmax(min_list)
    ans += min_list.popleft()
    # if index == len(min_list)-1:
    #     l, r = row[index], row[0]
    # else:
    #     l, r = row[index], row[index+1]
    # row.insert(index+1, A[i])
    min_list.append(A[i])
    min_list.append(A[i])
    # min_list.insert(index+1, A[i])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy

YES = "Yes"
NO = "No"

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

scores = [0] * K
pre = 0
for i in range(N):
    scores[i % K] = A[i]
    cur = numpy.prod(scores)

    if i >= K:
        if cur > pre:
            print(YES)
        else:
            print(NO)
    pre = cur


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"
NO = "No"

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

scores = [0] * K
scores[0] = A[0]
i = 1
while i < K:
    scores[i] = A[i]
    i += 1

while i < N:
    if A[i] > scores[i % K]:
        print(YES)
    else:
        print(NO)
    scores[i % K] = A[i]
    i += 1
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def sum_stair(n):
    num = 0
    for i in range(1, n + 1):
        num += i
    return num

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

    t = []
    for i in s:
        if i not in t:
            t.append(i)

    ans = 0
    for i in t:
        ans += max(0, sum_stair(s.count(i) - 1))
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def sort_str(t):
    l = sorted(t)
    text = ''
    for i in range(len(t)):
        text += l[i]
    return text

def sum_stair(n):
    num = 0
    for i in range(1, n + 1):
        num += i
    return num

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

    t = {}
    for i in s:
        t[i] = 0
    for i in s:
        t[i] += 1
    ans = 0
    for i in t.values():
        ans += sum_stair(i - 1)
    print(ans)

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

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    for l in range(n):
        if a[l]==i+1:
            b[i]=l+1
            break
print(*b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=[a[i],i+1]
b=sorted(b, key=lambda x: x[0])
for i in range(n):
    if i!=n-1:
        print(b[i][1],end=" ")
    else:
        print(b[i][1])
### BUGGY CODE ###

N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)

### FIXED CODE ###

N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)
### BUGGY CODE ###

if __name__ == "__main__":

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

    q = []
    reached = [[True]*(w+2)]
    for i in range(1, h+1):
      reached.append([True] + [s == '#' for s in list(input())] + [True])
      for j in range(1,w+1):
        if reached[i][j]: q.append((i,j))
    reached.append([True]*(w+2))

    res = 0
    head = 0
    tail = len(q)
    count = len(q)
    i = 0
    while tail - head > 0:
        k = q[head][0]
        l = q[head][1]
        if not reached[k+1][l]:
            q.append((k+1, l))
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            q.append((k, l+1))
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            q.append((k-1, l))
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            q.append((k, l-1))
            reached[k][l-1] = True
            tail += 1

        head += 1
        i += 1
        if i == count and tail - head > 0:
            count = tail - head
            i = 0
            res += 1
        else:
            pass

    print(res)


### FIXED CODE ###

def main():
  h,w = map(int,input().split())

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

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

from collections import deque
h,w = map(int,input().split())
grid = [['']*w for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    temp = list(input())
    grid[i] = temp
    for j in range(w):
        if temp[j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and d[nx][ny] == float('inf') and grid[nx][ny] == '.':
            d[nx][ny] = d[px][py] + 1
            ans = d[nx][ny]
            que.append([nx,ny])
print(ans)

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
a = []
d = []
que = deque()
for i in range(h):
    a.append(list(input()))
    d.append([1e100]*w)
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
            d[i][j] = 0
di = [-1,0,1,0]
dj = [0,1,0,-1]
ans = 0

while que:
    i,j = que.popleft()
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and d[ni][nj] == 1e100:
            d[ni][nj] = d[i][j] + 1
            ans = max(ans, d[ni][nj])
            que.append([ni,nj])
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in tergets:
			counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

from functools import reduce
import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

sum = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      sum += gcd(a, b, c)

print(sum)

### FIXED CODE ###

import math

k = int(input())

sum = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    ab = math.gcd(a,b)
    for c in range(1,k+1):
      sum += math.gcd(ab, c)

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

from functools import reduce

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

def others_xor(l, i):
  l.pop(i)
  return reduce(lambda acc, elem: acc ^ elem, l)

print(*[others_xor(xs[::], i) for i in range(N)])

### FIXED CODE ###

from functools import reduce

def problem():
  N = int(input())
  xs = [int(x) for x in input().split()]
  t = reduce(lambda acc, elem: acc ^ elem, xs)

  for i in range(N):
    yield (t ^ xs[i])

print(*problem())
### BUGGY CODE ###

# coding: utf-8

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

if n<=k:
    print(0)
else:
    for _ in range(k):
        h.remove(max(h))
    print(sum(h))

### FIXED CODE ###

# coding: utf-8

import sys
input=sys.stdin.readline

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

if n<=k:
    print(0)
else:
    h.sort()
    print(sum(h[:len(h)-k]))
### BUGGY CODE ###

n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    a,b=map(int,input().split())
    W.append(a)
    V.append(b)

dp=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if W[i]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-W[i]]+V[i])
print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    x,y=map(int,input().split())
    W.append(x)
    V.append(y)
dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if W[i]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-W[i]]+V[i])

print(dp[n][w])
### BUGGY CODE ###

def main():
    class rolling_hash():
        def __init__(self, seq):
            seq_size = len(seq)  # 文字列の長さ
            self.H0s = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            H0s, p = self.H0s, 0
            for i, j in enumerate(seq):
                p = (p+(j+1)*pow(3, i, mod)) % mod
                H0s[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            H0s = self.H0s
            return ((H0s[r]-H0s[l])*pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [0]*n
        a2 = [0]*n
        for i, j in enumerate(a):
            a1[i] = j % 2
            a2[i] = (j % 2) ^ 1
        a1 += a1
        a2 += a2
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        for i in range(n):
            a[i] //= 2
            b[i] //= 2

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()


### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

N, K = map(int, input().split())
tmp = input().split(' ')
A = []
for i in range(N):
    A = A + [int(tmp[i])]

for k in range(K):
    B = [0]*N
    for i in range(N):
        for j in range(N):
            if A[j] >= abs(j-i):
                B[i] = B[i]+1
    A = B

print(' '.join(map(str,A)))

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

from heapq import *
from collections import defaultdict

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    jobs[a].append(-b)

result = 0
pool = []
for i in range(1, m+1):
    pool += jobs[i]
    heapify(pool)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)

### FIXED CODE ###

from heapq import *
from collections import defaultdict

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    jobs[a].append(-b)

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)
### BUGGY CODE ###

from bisect import bisect

a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]

sentinel = lambda x: [-9e20] + x + [9e20]
s = sentinel(s)
t = sentinel(t)

for i in range(q):
    x = int(input())
    ss = bisect(s, x)
    tt = bisect(t, x)

    ll = max(s[ss], t[tt]) - x
    rr = x - min(s[ss-1], t[tt-1])
    rl = min((s[ss]- x) + s[ss] - t[tt-1], (t[tt]- x) + t[tt] - s[ss-1])
    lr = min((x - s[ss-1]) + t[tt] - s[ss-1], (x - t[tt-1]) + s[ss] - t[tt-1])

    print(min(ll, rr, rl, lr))

### FIXED CODE ###

import bisect
 
a, b, q = map(int, input().split())
s = sorted([int(input()) for i in range(a)])
t = sorted([int(input()) for i in range(b)])

s = [-9e20] + s + [9e20]
t = [-9e20] + t + [9e20]
 
for i in range(q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    m = bisect.bisect_left(t,x)
    
    ll = max(s[p], t[m]) - x
    lr = min(s[p] * 2 - t[m-1] - x, t[m] * 2 - s[p-1] - x)
    rl = min(s[p] - t[m-1] * 2 + x, t[m] - s[p-1] * 2 + x)
    rr = x - min(s[p-1], t[m-1])

    print(min(ll, lr, rl, rr))
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
N = 10**5
M = 13

s = input()
dp = np.zeros((N,M),dtype=np.int64)
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


print(dp[len(s),5])


### FIXED CODE ###

MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


print(dp[len(s)][5])
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
MAX_LENGTH = len(A)
#i番目以降の値を使ってmを作ればTrueを返す
def fullSearch(i, m):
    #終了条件
    if m == 0:
        return True
    elif i >= MAX_LENGTH:
        return False
    else:
        #全探索かっこわるい
        return fullSearch(i + 1, m) or fullSearch(i + 1, m - A[i])
 
for i in m:
    print("yes" if fullSearch(0, i) else "no")

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
MAX_LENGTH = len(A)
dp = [[-1 for i in range(max(m) + 1)] for j in range(MAX_LENGTH + 1)]
# i番目以降の値を使ってmを作ればTrueを返す
def fullSearch(i, m):
    # 終了条件
    if m < 0:
        return False
    elif dp[i][m] != -1:
        return dp[i][m]
    elif m == 0:
        return True
    elif i >= MAX_LENGTH:
        return False
    else:
        # 全探索かっこわるい
        res = fullSearch(i + 1, m) or fullSearch(i + 1, m - A[i])
    # のでメモ化
    dp[i][m] = res
    return res
for mi in m:
    print("yes" if fullSearch(0, mi) else "no")
### BUGGY CODE ###

H,W=map(int,input().split())
S=[[i for i in list(input())]for _ in range(H)]
L=[[1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            L[i][j]=0
        elif 0<j:
            L[i][j]=L[i][j-1]+1
R=[[1]*W for _ in range(H)]
for i in range(H):
    for j in range(W)[::-1]:
        if S[i][j]=="#":
            R[i][j]=0
        elif j<W-1:
            R[i][j]=R[i][j+1]+1
U=[[1]*W for _ in range(H)]
for i in range(W):
    for j in range(H):
        if S[j][i]=="#":
            U[j][i]=0
        elif 0!=j:
            U[j][i]=U[j-1][i]+1
D=[[1]*W for _ in range(H)]
for i in range(W):
    for j in range(H)[::-1]:
        if S[j][i]=="#":
            D[j][i]=0
        elif j!=H-1:
            D[j][i]=D[j+1][i]+1
ans=0
for i in range(H):
    for j in range(W):
        count=L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
        ans=max(ans,count)
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[[i for i in list(input())]for _ in range(H)]
L=[[0]*W for _ in range(H)]
R=[[0]*W for _ in range(H)]
U=[[0]*W for _ in range(H)]
D=[[0]*W for _ in range(H)]
for i in range(H):
    count=0
    for j in range(W):
        if S[i][j]=="#":
            count=0
        else:
            count=count+1
        L[i][j]=count
for i in range(H):
    count=0
    for j in range(W)[::-1]:
        if S[i][j]=="#":
            count=0
        else:
            count=count+1
        R[i][j]=count
for i in range(W):
    count=0
    for j in range(H):
        if S[j][i]=="#":
            count=0
        else:
            count=count+1
        U[j][i]=count
for i in range(W):
    count=0
    for j in range(H)[::-1]:
        if S[j][i]=="#":
            count=0
        else:
            count=count+1
        D[j][i]=count
ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(ans)
### BUGGY CODE ###

#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

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

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**11+1 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
#print(dp)

ans=0
for i in range(N+1):
    for sum_v in range(N*max(v)+1):
        if dp[i][sum_v]<=W:
            ans=max(ans,sum_v)
print(ans)   


### FIXED CODE ###

#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

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

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**12 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i+1]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]

ans=0

for sum_v in range(N*max(v)+1):
    if dp[N][sum_v]<=W:
        ans=max(ans,sum_v)
print(ans)
### BUGGY CODE ###

a = input()
q = input()
q = int(q)
reverse_count = 0
for i in range(q):
    que = input().split(" ")
    if que[0] == "1":
        reverse_count += 1
    else:
        if que[1] == "1":
            if reverse_count % 2 == 0:
                a = que[2]+a
            else:
                a += que[2]
        else:
            if reverse_count % 2 == 0:
                a += que[2]
            else:
                a = que[2]+a
if reverse_count % 2 == 1:
    a = a[::-1]
print(a)

### FIXED CODE ###

S = input()
N = input()
N = int(N)
re = False
foward = ""
back = ""

for i in range(N):
    que = input().split(" ")
    if que[0] == "1":
        if re:
            re = False
        else:
            re = True
    else:
        if re:
            if que[1] == "1":
                back += que[2]
            else:
                foward += que[2]
        else:
            if que[1] == "1":
                foward += que[2]
            else:
                back += que[2]
S = foward[::-1]+S+back
if re:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

s = list(str(input()))
q = int(input())

vec = 0
for _ in range(q):
    X = input().split()
    if X[0] == '1':
        vec = (vec+1) % 2
    else:
        if X[1] == '1' and vec == 0:
            s.insert(0, X[2])
        elif X[1] == '2' and vec == 0:
            s.append(X[2])
        elif X[1] == '1' and vec == 1:
            s.append(X[2])
        elif X[1] == '2' and vec == 1:
            s.insert(0, X[2])

if vec == 1:
    s.reverse()

print(''.join(map(str, s)))


### FIXED CODE ###

s = list(str(input()))
q = int(input())

from collections import deque
d = deque(s)
REVERSE = False

for _ in range(q):
    X = input().split()
    if X[0] == '1':
        REVERSE = not REVERSE
    else:
        if X[1] == '1' and not REVERSE:
            d.appendleft(X[2])
        elif X[1] == '2' and not REVERSE:
            d.append(X[2])
        elif X[1] == '1' and REVERSE:
            d.append(X[2])
        elif X[1] == '2' and REVERSE:
            d.appendleft(X[2])

if REVERSE:
    d.reverse()

print(*d, sep='')