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

import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    #node i is list of [child,size,comb] connected i
    #return [size,comb]
    @lru_cache(maxsize=1000000)
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        return (mysize+1,mycomb)

    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    for i in range(n):
        print(deep(i,-1)[1])

main()


### FIXED CODE ###

n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")
### BUGGY CODE ###

# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

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

for i in range(N):
    a[i] = a[i] - (i+1)

a.sort()
max = a[-1]
min = a[0]

for b in range(min, max + 1):
    sadness_left = 0
    i = 0
    while a[i] < b:
        sadness_left += b - a[i]
        i += 1
    sadness = sum(a) - b * N + sadness_left * 2
    if b == min:
        min_sadness = sadness
    elif min_sadness > sadness:
        min_sadness = sadness

print(min_sadness)


### FIXED CODE ###

# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

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

for i in range(N):
    a[i] = a[i] - (i+1)

a.sort()
if N % 2 != 0:
    mid = (N-1)//2
else:
    mid = N // 2 -1
b = a[mid]

sadness_left = b * mid - sum(a[:mid])
sadness = sum(a) - b * N + sadness_left * 2

print(sadness)
### BUGGY CODE ###

s = input()
a = "".join([chr(97 + i) for i in range(26)])
b = "".join([a[i -1] for i in range(26)])
x = str.maketrans(a, b)
while True:
    s = s.translate(x)
    if " the " in s or " that " in s or " this " in s:
        print(s)
        break


### FIXED CODE ###

import sys
a = "abcdefghijklmnopqrstuvwxyz"
x = str.maketrans(a, a[1:] + a[:1])
for s in sys.stdin:
    while True:
        s = s.translate(x)
        if "the" in s or "that" in s or "this " in s:
            print(s, end = "")
            break
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    ans += A[i] * sum(A[i+1:])

print(ans % ((10 ** 9) + 7))

### FIXED CODE ###

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

X = sum(A)
x = 0
ans = 0
for i in range(N):
    x += A[i]
    ans += A[i] * (X-x)

print(ans % ((10 ** 9) + 7))
### BUGGY CODE ###

N=int(input())

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

mul = 1
for i in A:
    mul = mul * i

if mul > 10 ** 18:
    mul = -1

print(mul)


### FIXED CODE ###

N=int(input())

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

mul = 1
for i in A:
    mul = mul * i
    if mul > 10 ** 18:
        mul = -1
        break

if 0 in A:
    mul = 0

print(mul)
### BUGGY CODE ###

n=int(input())
lst=[]
for i in range(n):
  a=int(input())
  if a in lst:
    lst.remove(a)
  elif a not in lst:
    lst.append(a)
print(len(lst))

### FIXED CODE ###

n=int(input())
s=set()
for i in range(n):s^={input()}
print(len(s))
### BUGGY CODE ###

n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)

while len(d):
    a, c = d.pop()
    if c == 1:
        count += 1
    if a == 1:
        break
    d = [elm for elm in d if elm[0] % a]

print(count)

### FIXED CODE ###

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

c = [0]*(10**6+1)

for a in aa:
    c[a] += 1

d = [False]*(10**6+1)

count = 0

for i in range(1, 10**6+1):
    if not c[i]:
        continue
    if d[i]:
        continue
    if c[i] == 1:
        count += 1
    for j in range(i, 10**6+1, i):
        d[j] = True

print(count)
### BUGGY CODE ###

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

#正解者順リスト
al = [int(input()) for i in range(q)]

#このリストのindex+1が参加者ナンバーです
#みんなの持ち点
nl = []
for m in range(n):
    nl.append(k)

for r in range(q):
    for x in range(n):
        nl[x] = nl[x]-1
#とりあえず全員、全正解数＊-1点する作業

for y in al:
    nl[y-1] = nl[y-1]+1

for z in nl:
    if z > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

#正解者順リスト
al = [int(input()) for i in range(q)]

#このリストのindex+1が参加者ナンバーです
#みんなの持ち点
nl = []
for m in range(n):
    nl.append(k-q)

for y in al:
    nl[y-1] = nl[y-1]+1

for z in nl:
    if z > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 1000000007
s = 0
for i in range(n):
    for j in range(i + 1, n):
        s += (a[i] * a[j]) % m
print(s % m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 1000000007
s = 0
suma = sum(a)
for i in range(n):
    suma -= a[i]
    s += a[i] * suma
print(s % m)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 1
c = int(1e18)
for i in range(n):
    b *= a[i]
if b>c:
    print(-1)
    exit()
print(b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 1
c = int(1e18)
flag = 0
for i in range(n):
    if a[i]==0:
        flag = 1
if flag==1:
    print(0)
    exit()
for i in range(n):
    b *= a[i]
    if b>c:
        print(-1)
        exit()
print(b)
### BUGGY CODE ###

import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 0:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

INF = 1<<32
    
def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[INF] * ((1<<N)+1) for i in range(M+1)]
    # for i in map(bin, c):
    #     print(i)

    dp[0][0] = 0
    for i in range(M):
        for j in range(1<<N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][j | c[i]] = min(dp[i+1][j | c[i]], dp[i][j]+a[i])

    # for i in dp:
    #     print(i)
    print(dp[M][(1<<N)-1] if (dp[M][(1<<N)-1]) < INF else -1)


# Generated by 1.1.5 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():
    # Failed to predict input format
    N, M = map(int, input().split())
    a = []
    b = []
    c = []
    for i in range(M):
        ax, bx = map(int, input().split())
        cx = map(int, input().split())
        a.append(ax)
        b.append(bx)
        ct = 0
        for j in cx:
            ct |= (1<<(j-1))
        c.append(ct)
    solve(N, M, a, b, c)

    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
  N,M=map(int,input().split())
  Inf=10**8
  dp=[Inf]*(2**N)
  dp[0]=0
  for i in range(M):
    a,b=map(int,input().split())
    tmp=list(map(int,input().split()))
    open_tresure=list(1<<j-1 for j in tmp)
   # print(open_tresure)
    op_tr=sum(open_tresure)
    for j in range(2**N):
      key=op_tr | j
      dp[key]=min(dp[key],dp[j]+a)
  if dp[-1]==Inf:
    print(-1)
  else:
    print(dp[-1])

main()
### BUGGY CODE ###

a = int(input())
num  = 0
for i in range(1,a):
    num += i
print(num)

### FIXED CODE ###

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

N = int(input())
A = list(map(int, input().split()))
count = 0
Flag = 1
while Flag:
    flag = 0
    for i in range(N-1, 1):
        if(A[i] < A[i-1]):
            temp = A[i-1]
            A[i-1] = A[i]
            A[i] = temp
            flag = 1 
            count += 1
print(*A)
print(count)
            

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
flag = True
while flag:
    flag = False
    for i in range(N-1, 0, -1):
        if(A[i] < A[i-1]):
            A[i], A[i-1] = A[i-1], A[i]
            flag = True
            count += 1
print(*A)
print(count)
### BUGGY CODE ###

nkc=list(map(int, input().split()))
s=input()
n=nkc[0]
k=nkc[1]
c=nkc[2]
for i in range(len(s)):
    if s[i]=='o':
        sw=s
        sw=sw[:i]+'x'+sw[i+1:]
        counter=0
        num=0
        while counter<k and num<n:
            #print(num)
            if sw[num]=='o':
                counter+=1
                num+=c+1
            else:
                num+=1
        if counter<k:
            print(i+1)

### FIXED CODE ###

nkc=list(map(int, input().split()))
s=input()
n=nkc[0]
k=nkc[1]
c=nkc[2]
l=[]
r=[]
onum=sum(1 for i in range(len(s)) if s[i]=='o')
num=0
counter=0
while counter<k and num<n:
    #print(num)
    if s[num]=='o':
        l.append(num)
        counter+=1
        num+=c+1
    else:
        num+=1
num=n-1
counter=0
while counter<k and num>=0:
    #print(num)
    if s[num]=='o':
        r.append(num)
        counter+=1
        num-=c+1
    else:
        num-=1
#print(l)
#print(r)
lenr=len(r)
for i in range(min(lenr, len(l))):
    if r[lenr-i-1]==l[i]:
        print(l[i]+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
# print('A:',A)

from itertools import product
a=[0,1]  #0:buy  1:sell
Ls = list(product(a, repeat=N-1))
# print('Ls:',Ls)

out=0
for L in Ls:
    # print('L:',L)
    money=1000
    kabu=0
    for i in range(N-1):
        if L[i]==0:
            kabu+=money // A[i]
            money=money % A[i]

        else:
            money+=kabu*A[i]
            kabu=0
        # print('money,kabu:',money,kabu)
    money+=kabu*A[N-1]  #last
    out=max(out,money)

print(out)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
# print('A:',A)
money=1000
kabu=0

for i in range(N-1):
    if A[i] < A[i+1]:
        kabu+=money // A[i]
        money=money % A[i]
    elif A[i] > A[i+1]:
        money+=kabu*A[i]
        kabu=0
money+=kabu*A[N-1]  #last

print(money)
### BUGGY CODE ###

n, w = map(int, input().split())
W, V =[0]*n, [0]*n
for i in range(n):
  W[i],V[i] = map(int, input().split())

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

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

### FIXED CODE ###

n, w = map(int, input().split())
W, V =[0]*n, [0]*n
for i in range(n):
  W[i],V[i] = map(int, input().split())

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

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

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
m = max(a)
for j in a:
  if j < m:
    print(m)
  elif j == m:
    b = sorted(a.copy())
    print(b[n-2])
    
  

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
b = a.copy()
m = max(a)
b2 = b.remove(m)
mb = max(b)
for j in a:
  if j < m:
    print(m)
  elif j == m:
    print(mb)
### BUGGY CODE ###

def calc_double(n):
    return n * 2

def main():
    N = int(input())
    S = input()
    r = []
    g = []
    b = []
    answer = 0

    for i in range(len(S)):
        # print(S[i])
        if S[i] == 'R':
            r.append(i)
            continue
        if S[i] == 'G':
            g.append(i)
            continue
        b.append(i)


    # print(r)
    # print(g)
    # print(b)
    # print()
    rg = [(i+j) for i in r for j in g]
    gb = [(i+j) for i in g for j in b]
    br = [(i+j) for i in b for j in r]

    # for i in r:
    #     if i in gb: answer += 1
    #
    # for i in g:
    #     if i in br: answer += 1
    #
    # for i in b:
    #     if i in rg: answer += 1
    #
    # print("answer")
    # print(answer)
    # print()

    r = list(map(calc_double, r))
    g = list(map(calc_double, g))
    b = list(map(calc_double, b))


    for i in gb:
        if i in r: answer += 1

    for i in br:
        if i in g: answer += 1

    for i in rg:
        if i in b: answer += 1
    #
    # print("answer")
    # print(answer)
    # print()
    #
    # rg.sort()
    # print(rg)
    # print(b)
    # print()
    # gb.sort()
    # print(gb)
    # print(r)
    # print()
    # br.sort()
    # print(br)
    # print(g)
    #
    # print(len(set(rg) & set(b)))
    # print(len(set(gb) & set(r)))
    # print(len(set(br) & set(g)))

    print(len(r) * len(g) * len(b) - answer)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from time import time

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

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

    for i in range(N):
        for j in range(i, N):
            k = 2*j - i
            if k >= N: continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]: answer -= 1
    print(answer)

if __name__ == '__main__':
    start = time()
    main()
    # print(time() - start)
### BUGGY CODE ###

n,w = map(int,input().split())
dpv = [10 ** 20 for i in range(10**5+1)]
dpv[0] = 0
for i in range(n):
  weight,value = map(int,input().split())
  for j in range(10**5-value,-1,-1):
    dpv[j+value] = min(dpv[j+value],dpv[j]+weight)
for i in range(10**5,-1,-1):
  if dpv[i] <= w:
    print(i)
    exit()

### FIXED CODE ###

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

lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])

dp = {0:0}

for weight ,value in lis:
    gone = dp.copy()
    for key in dp:
        gone[key+value] = min(dp[key] + weight, dp.get(key+value, float("inf")))
    dp = gone
for key in sorted(dp.keys(), reverse = True):
    if dp[key] <= w:
        print(key)
        exit()
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
f = []
for i in range(a, b+1):
  for j in range(c, d+1):
    e = i * j
    f.append(e)
print(max(f))    
  

### FIXED CODE ###

a,b,c,d=list(map(int,input().split()))
x=[a*c,a*d,b*c,b*d]
print(max(x))
### BUGGY CODE ###

import sys

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

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0

for w,c in cf:
    for j in reversed(range(w, we+1)):
        if dp[j]<dp[j-w]+ c : dp[j]=dp[j-w]+ c
    # print(dp)
    best=max(best, dp[we])


print(best)

### FIXED CODE ###

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

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

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )
### BUGGY CODE ###

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ma = 0
    a2 = [0]
    b2 = [0]
    for i in range(len(a)):
        a2.append(a[i]+a2[i])
    for i in range(len(b)):
        b2.append(b[i]+b2[i])

    for i in range(len(a2)):
        cnt = i
        if(a2[i]>k):
            break
        j = len(b2) -1
        while((a2[i]+b2[j])>k):
            j -= 1
        ma = max(ma,i+j)

    print(ma)
            
main()

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

def kitai(l):
  return (l+1)/2

n , k = map(int, input().split())
a = list(kitai(int(i)) for i in input().split())


max_ = 0
for i in range(n-k+1):
  max_ = max(max_, sum(a[i:i+k]))
    
print(max_)

### FIXED CODE ###

n , k = map(int, input().split())
a = list(int(i) for i in input().split())
 
temp = sum(a[0:k])
max_  = temp
for i in range(n-k):
  f = a[i]
  s = a[i+k]
  temp -= f
  temp += s
  max_ = max(max_, temp)
    
print((max_+k)/2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, fractions, itertools

def solve(N: int, A: int, x: "List[int]"):
    X = max(x)
    dp = [[[0 for _ in range(max(N*X+1, N*A+1))] for _ in range(N+1) ] for _ in range(N+1)]
    dp[0][0][0] = 1
    for n in range(N+1):
        for m in range(N+1):
            for k in range(N*X+1):
                if n >= 1 and k < x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k]
                elif n >= 1 and m >= 1 and k >= x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k] + dp[n-1][m-1][k-x[n-1]]
    s = 0
    for i in range(1, N+1):
        s += dp[N][i][i*A]
    print(s)
    return


# Generated by 1.1.4 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
    A = int(next(tokens))  # type: int
    x = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, fractions, itertools

def solve(N: int, A: int, x: "List[int]"):
    X = max(x)
    dp = [[[0 for _ in range(max(N*X+1, N*A+1))] for _ in range(N+1) ] for _ in range(N+1)]
    dp[0][0][0] = 1
    for n in range(N+1):
        for m in range(N+1):
            for k in range(N*X+1):
                if n >= 1 and k < x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k]
                elif n >= 1 and m >= 1 and k >= x[n-1]:
                    dp[n][m][k] = dp[n-1][m][k] + dp[n-1][m-1][k-x[n-1]]
    s = 0
    for i in range(1, N+1):
        s += dp[N][i][i*A]
    print(s)
    return


# Generated by 1.1.4 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
    A = int(next(tokens))  # type: int
    x = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, x)

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

n=int(input())
ans=0
if n==1:
  print(0)
else:
  for i in range(1,n):
    ans+=i
  print(ans)

### FIXED CODE ###

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

S=input()
N=len(S)
R=[0]*(N+1)
for i in range(1,N+1):
    R[-(i+1)]=((int(S[-i])*10**(i-1))%(2019)+R[-i])%2019
#print(R)
L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)



### FIXED CODE ###

S=input()
N=len(S)
R=[0]*(N+1)
mul=1
for i in range(1,N+1):
    R[-(i+1)]=(((int(S[-i])*mul))%(2019)+R[-i])%2019
    mul*=10
    mul%=2019
#print(R)
L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field=[[[0 for h in range(6500)] for i in range(w+1)] for j in range(h+1)]
field[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]==1:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=1
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=1
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=1
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=1
for i in range(6500):
    if field[h-1][w-1][i]==1:print(i);exit()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field=[[[0 for h in range(6500)] for i in range(w+1)] for j in range(h+1)]
field[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]==1:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=1
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=1
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=1
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=1
for i in range(6500):
    if field[h-1][w-1][i]==1:print(i);exit()
### BUGGY CODE ###

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

def dp(N,W):
    ans=np.zeros(W+1,dtype=np.int)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=ans[i-w]+v
            if ans[i]<tmp:
                ans[i]=tmp
    print(ans[-1])

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

### FIXED CODE ###

def opt(N,W):
    dp=[0]*(W+1)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=dp[i-w]+v
            if tmp>dp[i]:
                dp[i]=tmp
    print(dp[W])

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