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

#問題 D
N, W = map(int,input().split())
VAL = [0]*(W+1)
val = [0]*(W+1)
for n in range(N):
    w,v = map(int,input().split())
    for weight in range(1,W+1):
        if weight >= w:
            val[weight] = max(VAL[weight],VAL[weight-w]+v)
    VAL = val[:]
print(VAL[W])
    # listをコピーするときは注意　https://qiita.com/utgwkk/items/5ad2527f19150ae33322

### FIXED CODE ###

import numpy as np
N, W = map(int,input().split())
#普通に書くとTLEだったのでNumpy化
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:] = np.maximum(dp[w:],dp[:-w]+v)
print(int(dp[-1]))
### BUGGY CODE ###

# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import numpy as np
import bisect
n = int(input())
a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
# s = 0
# for i,num in enumerate(a):
#     s += a[i]
#     ca[i] = s
ca = a.cumsum()

def sub(l, init):
    if len(l)==0:
        return 0,0
    elif len(l)==1:
        return 0,l[0]-init
    target = (init + l[-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[-1]-l[i])
    p2 = (l[i-1]-init, l[-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca[:i], 0)
    p2 = sub(ca[i:], ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
    best = min(best, nn)
print(best)

### FIXED CODE ###

# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


# import numpy as np
import bisect
n = int(input())
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
# ca = a.cumsum()

def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)
### BUGGY CODE ###

import math
N,L=map(int,input().split())
T=[int(input()) for i in range(N)]
X=0
Y=0
for i in range(N):
    for j in range(i+1,N):
        angle=math.pi*(T[j]+T[i])/L
        #print(math.cos(angle),math.sin(angle))
        X+=math.cos(angle)*(N-2-(j-i-1)*2)
        Y+=math.sin(angle)*(N-2-(j-i-1)*2)
A=(N*(N-1)*(N-2))//6
print(X/A,Y/A)


### FIXED CODE ###

import math
N,L=map(int,input().split())
T=[int(input()) for i in range(N)]
X=0
Y=0
for i in range(N):
    for j in range(i+1,N):
        angle=math.pi*(T[j]+T[i])/L
        #print(math.cos(angle),math.sin(angle))
        X+=math.cos(angle)*(N-2-(j-i-1)*2)
        Y+=math.sin(angle)*(N-2-(j-i-1)*2)
A=(N*(N-1)*(N-2))//6
print(X/A,Y/A)
### BUGGY CODE ###

import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
XN = len(tmp)
st = SegTree([XN]*XN, XN, XN, min)
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q < t:
                if c != XN:
                    print(tmp[c])
                else:
                    print(-1)
                Q-=1
                if Q == 0:
                    break
                q = int(input())
            else:
                break
#    print(t,r,x)
    if Q==0:
        break
    if r:
        st.update(x2i[x], x2i[x])
    else:
        st.update(x2i[x], XN)
print("-1\n"*Q)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

ks = input().split()

k = int(ks[0])
s = int(ks[1])

ans = 0

for x in range(k+1):
	for y in range(k+1):
		for z in range(k+1):	
			if x + y + z == s:
				ans += 1
				break
		
print(ans)

### FIXED CODE ###

ks = input().split()

k = int(ks[0])
s = int(ks[1])

ans = 0

for x in range(k+1):
	for y in range(k+1):
			tmp = s - (x + y)
			if tmp  <= k and tmp >= 0:
				ans += 1
		
print(ans)
### BUGGY CODE ###

n= int(input())
l = list(map(int,input().split()))
ans = 0
L = sorted(l, reverse=True)

for i in range(n-2):
    for j in range(i+1, n-1):
        ans += len([x for x in L[j+1:] if x + L[j] > L[i]])
    
print(ans)


### FIXED CODE ###

import bisect

n= int(input())
l = list(map(int,input().split()))
ans = 0
L = sorted(l)

for i in range(n-2): # max
    for j in range(i+1, n-1): # second max
        index = bisect.bisect_left(L[j+1:], L[i]+L[j])
        ans += index
    
print(ans)
### BUGGY CODE ###

from fractions import Fraction

def main():
    N = int(input())
    a = Fraction(4, N)
    ans = [0,0,0]
    for h in range(N//2,3501):
        b = Fraction(1, h)
        for n in range(N//2,3501):
            c = Fraction(1,n)
            d = a - b - c
            if d > 0 and d.numerator == 1:
                print(h, n, d.denominator)
                exit()






if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N = int(input())
    for h in range(1,3501):
        for n in range(1,3501):
            if 4 * h * n - N * n - N * h == 0:
                continue
            w = (N * h * n) / (4 * h * n - N * n - N * h)
            if w > 0 and w.is_integer():
                print(h,n,int(w))
                exit()




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

import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
data = collections.Counter(a)
count, key = list(data.values()), list(data.keys())

for i in range(q):
    b, c = map(int, input().split())
    if b in key and c in key:
        count[key.index(c)] += count[key.index(b)]
        count[key.index(b)] = 0
    elif b in key:
        key.append(c)
        count.append(count[key.index(b)])
        count[key.index(b)] = 0
    res = 0
    for j in range(len(key)):
        res += count[j] * key[j]
    print(res)




### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
data = [0] * (10**5 + 1)

for i in a:
    data[i] += 1
res = sum(a)

for j in range(q):
    b, c = map(int, input().split())
    res += (c - b) * data[b]
    data[c] += data[b]
    data[b] = 0
    print(res)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([c])
passed = set()
queued = set()
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()
        if (h,w) in passed:
            continue
        passed.add((h,w))
        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in queued and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))
                queued.add((nh,nw))

        for dh,dw in [
            [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
            [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
            [0,-2], [0, 2], 
            [1,-2], [1,-1], [1, 1], [1, 2], 
            [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
        ]: 
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in nque and (nh,nw) not in queued and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

### FIXED CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([(*c, 0)])
passed = set()
while que:
    h,w,dist = que.popleft()
#         print(f'{h=},{w=}')
    if (h,w) == d:
        print(dist)
        exit()
    if (h,w) in passed:
        continue
    passed.add((h,w))
    for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
            que.appendleft((nh, nw, dist))

    for dh,dw in [
        [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
        [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
        [0,-2], [0, 2], 
        [1,-2], [1,-1], [1, 1], [1, 2], 
        [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
    ]: 
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
            que.append((nh, nw, dist + 1))
print(-1)
### BUGGY CODE ###

x = int(input())
a = 0
b = 0
b2 = 0
judge = 0

"""while a**5 - b**5 < 10**9:
    while a**5 - b**5 > 0:
        if a**5 - b**5  == x:
            judge = 1
            print(a ,b)
            break
        b += 1
    else:
        a += 1
        continue
    break
"""
if judge == 0:
    a = 0
    while a**5 - b2**5 < 10**9:
        while a**5 - b2**5 > 0:
            if a**5 - b2**5  == x:
                print(a ,b2)
                break
            b2 -= 1
        else:
            a += 1
            continue
        break





### FIXED CODE ###

x = int(input())
a = 0

while True:
    b = 0
    b2 = 0
    while a**5 - b**5 > 0 or a**5 - b2**5 < 10**9:
        if a**5 - b**5  == x:
            print(a ,b)
            break
        b += 1
        if a**5 - b2**5 == x:
            print(a ,b2)
            break
        b2 -= 1
    else:
        a += 1
        continue
    break
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Lazy Faith
https://atcoder.jp/contests/abc119/tasks/abc119_d

"""
import sys
from bisect import bisect_left, bisect_right

def solve(x):
    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    ans1 = max(ds, dt)

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_left(temples, x)
    dt = temples[j] - x
    ans2 = max(ds, dt)

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    ans3 = min(ds, dt) * 2 + max(ds, dt)

    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_left(temples, x)
    dt = temples[j] - x
    ans4 = min(ds, dt) * 2 + max(ds, dt)

    return min(ans1, ans2, ans3, ans4)


shrines = None
temples = None

def main(args):
    global shrines, temples
    A, B, Q = map(int, input().split())
    shrines = sorted([int(input()) for _ in range(A)] + [float('-inf'), float('inf')])
    temples = sorted([int(input()) for _ in range(B)] + [float('-inf'), float('inf')])
    for _ in range(Q):
        x = int(input())
        ans = solve(x)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Lazy Faith
https://atcoder.jp/contests/abc119/tasks/abc119_d

"""
import sys
from bisect import bisect_left, bisect_right

def solve(shrines, temples, x):
    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    ans = max(ds, dt)

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_left(temples, x)
    dt = temples[j] - x
    ans = min(ans, max(ds, dt))

    i = bisect_left(shrines, x)
    ds = shrines[i] - x
    j = bisect_right(temples, x)
    dt = x - temples[j-1]
    d = min(ds, dt) * 2 + max(ds, dt)
    ans = min(ans, d)

    i = bisect_right(shrines, x)
    ds = x - shrines[i-1]
    j = bisect_left(temples, x)
    dt = temples[j] - x
    d = min(ds, dt) * 2 + max(ds, dt)
    ans = min(ans, d)

    return ans


def main(args):
    A, B, Q = map(int, input().split())
    shrines = sorted([int(input()) for _ in range(A)] + [float('-inf'), float('inf')])
    temples = sorted([int(input()) for _ in range(B)] + [float('-inf'), float('inf')])
    for _ in range(Q):
        x = int(input())
        ans = solve(shrines, temples, x)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

import itertools

n=int(input())
ls=[]
for i in range(n):
  ls.append(i+1)
k=ls
k.pop(0)
k.append(1)

max=0
for l in ls:
  max+=l%k[l-1]
print(max)
  


### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

n = inp()
print(int((n-1)*n//2))

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)
### BUGGY CODE ###

n = int(input())

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

count = 0

for i in range(n):
  correct = True
  for j in range(i+1):
    
    if p[i] > p[j]:
      correct = False
      break;
  
  if correct:
    count += 1
    
print(count)

### FIXED CODE ###

n = int(input())

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

count = 0
min = p[0]

for i in range(n):
  if p[i] <= min:
    min = p[i]
    count += 1
    
print(count)
### BUGGY CODE ###

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

A.sort(reverse=True)

for i in range(M):
    A[0] = A[0]/2
    A.sort(reverse=True)

ans = 0
print(sum([int(i) for i in A]))




### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda a: int(a)*(-1), input().split()))

heapq.heapify(A)

for i in range(M):
    a = -heapq.heappop(A)//2
    heapq.heappush(A, -a)
    
print(-sum(A))
### BUGGY CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')

ans=r*g*b
dib=0


for i in range(N-2):
    for j in range(i+1,N):
        if S[j]!=S[i]:
            dib=j-i
            if j+dib<=N-1:
                if S[i]!=S[j+dib] and S[j]!=S[j+dib]:
                    ans=ans-1
            
print(ans)

### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')


ans=r*g*b
dib=0
m=0

for i in range(N-2):
    m=(N+i)//2+1
    for j in range(i+1,m):
            dib=j-i
            if j+dib<=N-1:
                if S[i]!=S[j] and S[i]!=S[j+dib] and S[j]!=S[j+dib]:
                    ans=ans-1
            
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[i] for i in range(N)]  # 各頂点の持つ部分木の頂点の集合
edges = [list(map(int, input().split())) for _ in range(N-1)][::-1]
counts = np.zeros(N, dtype=np.int32)

for a, b in edges:
    children[a-1] += children[b-1]

for _ in range(Q):
    p, x = map(int, input().split())
    counts[children[p-1]] += x

for count in counts:
    print(count, end=' ')

### FIXED CODE ###

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

def main():
    N, Q = map(int, input().split())
    # edges = [None]*N
    edges = [[] for _ in range(N)]
    # edges[0] = 0
    # edges[0].append = 0
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[b-1].append(a-1)
        edges[a-1].append(b-1)

    counts = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        counts[p-1] += x

    parent_nodes = deque()
    parent_nodes.append(0)
    visited_nodes = set()
    while parent_nodes:
        parent = parent_nodes.popleft()
        if parent in visited_nodes:
            continue
        visited_nodes.add(parent)
        for child in edges[parent]:
            if child in visited_nodes:
                continue
            counts[child] += counts[parent]
            parent_nodes.append(child)

    print(' '.join(list(map(str, counts))))

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

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
k = int(input())
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            sum += gcd(i,j,l)
print(sum)


### FIXED CODE ###

import math
#from functools import reduce
#def gcd(*numbers):
#    return reduce(math.gcd, numbers)
k = int(input())
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            sum += math.gcd(math.gcd(i,j),l)
print(sum)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

MOD = 10**9 + 7
res = [0] * (n+1)
res[0] = 1
res[1] = 1 if 1 not in a else 0

for i in range(2, n+1):
    if i in a:
        continue

    # 到達不可能
    if res[i-1] == 0 and res[i-2] == 0:
        break

    res[i] = res[i-1] + res[i-2]

print(res[-1]%MOD)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [0] * (n+1)
for _ in range(m):
    a[int(input())] = -1

MOD = 10**9 + 7
res = [0] * (n+1)
res[0] = 1
res[1] = 0 if a[1] == -1 else 1

for i in range(2, n+1):
    if a[i] == -1:
        continue

    # 到達不可能
    if res[i-1] == 0 and res[i-2] == 0:
        break

    res[i] = (res[i-1] + res[i-2]) % MOD

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

n,m=map(int,input().split())
lista = [int(i) for i in input().split()]
lista.sort()

dic = {}
for i in range(31):
    dic[i] = []

i2 = 0

for i in range(len(lista)):
    while(lista[i]>=2**(i2+1)):
        i2+=1
    dic[i2].append(lista[i])
    
#print(dic)

end = False
for t in range(i2,0,-1):
    list_d = dic[t]
    list_d.sort()
    loop = len(list_d)
    if loop<m:
        for i in range(loop):
            list_d[i] = list_d[i]/2
        dic[t-1] = dic[t-1]+list_d
        list_d = []
        m = m-loop
    else:
        for i in range(loop):
            tmp = list_d[-1]
            dic[t-1].append(tmp/2)
            list_d =  list_d[:-1]
            m = m-1
            if m==0:
                end = True
                dic[t] = list_d
                break

    dic[t] = list_d
    if end == True:
        break
        
        
"""print(dic)
print(m)"""
ans = 0
if m > 0:
    ans = n-m
    if ans >= 0:
        print(n-m)
    else:
        print(0)
else:
    for i in range(t+1):
        list_d = dic[i]
        #print(i,list_d)
        for l in range(len(list_d)):
            tmp = list_d[l]
            ans+=int(tmp)
    print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x * (-1), a))
heapq.heapify(a)
while m != 0:
    price = heapq.heappop(a)
    price = price/2
    m -= 1
    heapq.heappush(a, price)

for i in range(len(a)):
    a[i] = int(a[i])
print(sum(a) * (-1))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
aset = set(a)
aset = sorted(aset, reverse = True)
res = 0
for i in aset:
    count = a.count(i)
    if count >= 4 and res == 0:
        print(i*i)
        exit()
    elif count >= 2 and res == 0:
        res = i
    elif count >= 2:
        print(res * i)
        exit()
print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
aset = set(a)
d = {i:0 for i in aset}
for i in range(n):
    d[a[i]] += 1

res = 0
for k, i in sorted(d.items(), reverse = True):
    if i >= 4 and res == 0:
        print(k*k)
        exit()
    elif i >= 2 and res == 0:
        res = k
    elif i >= 2:
        print(res * k)
        exit()
print(res)
### BUGGY CODE ###

def main():
    N = int(input())

    for n in range(1, 3501):
        for h in range(1, 3501):
            if 4 * h * n - N * n - N * h != 0:
                w = N * h * n / (4*h*n - N * n - N * h)
                if w.is_integer() and w > 0:
                    print("{} {} {}".format(n, h, int(w)))
                    exit()

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())

    for n in range(1, 3501):
        for h in range(1, 3501):
            b = 4 * h * n - N * n - N * h
            if b > 0:
                w = N * h * n / b
                if w.is_integer():
                    print("{} {} {}".format(n, h, int(w)))
                    exit()

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

import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
    
    @lru_cache(maxsize=None)
    def dfs(w, v, i):
        if w > W:
            return 0
        if i >= N:
            return v
        return max(dfs(w + w_v[i][0], v + w_v[i][1], i+1), dfs(w, v, i+1))

    res = dfs(0, 0, 0)
    print(res)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    for i in range(N-1,-1,-1):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w_v[i][0]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j - w] + v)
 
    print(dp[0][W])
 
if __name__ == "__main__":
    resolve()