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

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

counts = {}
for i in range(N):
    a = A[i]
    if a in counts:
        counts[a] += 1
        continue
    counts[a] = 1

# print(counts)

for k in range(N):
    counts_tmp = counts.copy()
    counts_tmp[A[k]] -= 1

    # print(counts_tmp)
    ans = 0
    for v in counts_tmp.values():
        ans += v * (v - 1) // 2
    print(ans)


### FIXED CODE ###

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

counts = {}
for i in range(N):
    a = A[i]
    if a in counts:
        counts[a] += 1
    else:
        counts[a] = 1

# print(counts)

ans_memory = {}
ans_memory_val = {}
for k in range(N):
    if A[k] in ans_memory:
        print(ans_memory[A[k]])
        continue
    if counts[A[k]] in ans_memory_val:
        print(ans_memory_val[counts[A[k]]])
        continue

    counts_tmp = counts.copy()
    counts_tmp[A[k]] -= 1

    # print(counts_tmp)
    ans = 0
    for v in counts_tmp.values():
        ans += v * (v - 1) // 2
    ans_memory[A[k]] = ans
    ans_memory_val[counts[A[k]]] = ans
    print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s):
    if 'LOCAL' in os.environ:
        print(s)

def main():
    global AB, PX, T
    if 'BIG' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        #  AB = []
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(N-1):
            a, b = LI()
            #  AB += (a, b)
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        #  perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    perr(PX)
    for node in T[parent]:
        if node != parent_parent:
            perr(node)
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
for a, b in AB:
    if b not in d.keys():
        d[b] = 0
    if a not in d.keys():
        d[a] = 0
    d[b] += d[a]
for i in range(1, N+1):
    print(d[i], end=' ')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
list1 = list(input())
del list1[-1]
ans = 0
def func(flist):
    i = 0
    flag = 0
    global ans
    while len(flist)>i+1:
        if flist[i] != flist[i+1]:
            flag = 1
            del flist[i],flist[i]
            ans += 1
        else:
            i+=1
    if not flag:
        return False
    else:
        return True
if __name__ == "__main__":
    while True:
        if not func(list1):
            break
    print(ans*2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
list1 = list(input())
del list1[-1]
ans = 0
def func(flist):
    count0 = 0
    for i in flist:
        if i == "0":
            count0 += 1
    count1 = len(flist)-count0
    return len(flist)-abs(count1-count0)

if __name__ == "__main__":
    print(func(list1))
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
ans=1
LIMIT=10**18
for i in range(n):
  ans*=A[i]
if ans>LIMIT:
  ans=-1
print(ans)


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
ans=1
LIMIT=10**18

if 0 in A:
  print(0)
else:
  for i in range(n):
    ans*=A[i]
    if ans>LIMIT:
      ans=-1
      break
  print(ans)
### BUGGY CODE ###

S=input()

for i in range(len(S)):
  if S[i]=="?":
    S= S[:i]+"D"+S[i+1:]
    
print(S)

### FIXED CODE ###

S=input()

S=S.replace("?","D")    
print(S)
### BUGGY CODE ###

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

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    value = 10 ** 10
    for j in range(1, min(k + 1, n)):
        cost = abs(h[i] - h[i - j])
        value = min(value, dp[i - j] + cost)
    dp[i] = value

print(dp[n - 1])


### FIXED CODE ###

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

dp = [10 ** 10] * (n + k)
h += [10 ** 10] * k
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        cost = abs(h[i] - h[i + j])
        dp[i + j] = min(dp[i + j], dp[i] + cost)

print(dp[n - 1])
### BUGGY CODE ###

N = int(input())
ret = []
for i in range(N):
    s = input()
    if s not in ret:
        ret.append(s)
print(len(ret))

### FIXED CODE ###

N = int(input())
ret = {}
for i in range(N):
    ret[input()] = 0
print(len(ret.keys()))
### BUGGY CODE ###

import math


def main():
    N = int(input())
    A = []
    B = []

    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    c = 0
    while A != B:
        minc = 999999999999
        minc_idx = None
        for i in range(N):
            if A[i] < minc and A[i] != 0:
                minc = A[i]
                minc_idx = i
        A[minc_idx] -= 1
        diff = 999999999999
        diff_idx = None
        for i in range(N):
            if A[i] < diff and B[i] != 0:
                diff = A[i]
                diff_idx = i
        B[diff_idx] -= 1
        c += 1
        # print(A, minc_idx)
        # print(B, diff_idx)

    print(c)


if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
if A == B:
  print(0)
else:
  M = sum(A)
  c = 10**10
  for a, b in zip(A, B):
    if a > b:
      c = min(c, b)
  print(M - c)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

# 無限大の値
f_inf = float('inf')

# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)

# 初期条件
dp[0] = 0

# 足場 i-1 から足場 i へと移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
# 足場 i-j から足場 i へと移動する。コストは |h[i]−h[i-j]|
for i in range(1, n):
    for j in range(max(i-k, 0), i):
        dp[i] = chmin(dp[i], dp[j] + abs(h[i] - h[j]))

print(dp[n-1])



### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = np.zeros(n, dtype=int)
h = np.array(h)


for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x

def lcm(x, y):
    return x//gcd(x, y)*y

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

l = 1
for x in a:
    l = lcm(x, l)

ans = 0
for x in a:
    ans += l//x

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


### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))
### BUGGY CODE ###

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()))

AB=[]
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
        
AB.sort(reverse=True)
tmp=AB[0:min(3001,len(AB))]

ABC=[]
for i in range(len(tmp)):
    for j in range(Z):
        ABC.append(tmp[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED CODE ###

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

ABC=[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1)<=K:
                ABC.append(A[i] + B[j] + C[k])
            else:
                break

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

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

for i in range(N):
  a = 0
  for j in range(N//2):
    a += A[(i+j*2+1)%N]
  print(s-a*2, end=" ")
  
print("")

### FIXED CODE ###

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

n = [0]*N
n[0] = sum(A)-sum(A[1::2])*2
print(n[0], end = " ")

for i in range(N-1):
  n[i+1] = A[i]*2-n[i]
  print(n[i+1], end = " ")

print("")
### BUGGY CODE ###

s = input()
t = input()
ls=len(s)
lt=len(t)

#sの文字数行*tの文字数列のDP
import numpy as np
dp=[[0]*(lt+1) for _ in range(ls+1)]
dp=np.array(dp)

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1]==t[j-1]:
        # sとtの見た文字が一致
        # →sとtの双方の1個前までの共通最大連続数に+1追加
            dp[i][j]=dp[i-1][j-1]+1
        else:
        # 一致しないとき
        # sの1個前までか、tの1個前の共通最大連続数の
        # 大きいほうを採用
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

# 復元はs,tとも後ろから見ていく
ans = ''
i=ls
j=lt
while i != 0 and j != 0:
    if dp[i][j] == dp[i-1][j]:
        # DP上でsの一個前から更新されてない
        # 即ちs[i-1]は共通列に入ってない
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # 上と同じ論法でtの場合
        j -= 1
    else:
        # 今見ているs[i-1]とt[j-1]が共通になっているとき
        # 答えに採用（s[i-1]は頭につける）
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
        
print(ans)

### FIXED CODE ###

s = input()
t = input()
ls=len(s)
lt=len(t)

#sの文字数行*tの文字数列のDP
dp=[[0]*(lt+1) for _ in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1]==t[j-1]:
        # sとtの見た文字が一致
        # →sとtの双方の1個前までの共通最大連続数に+1追加
            dp[i][j]=dp[i-1][j-1]+1
        else:
        # 一致しないとき
        # sの1個前までか、tの1個前の共通最大連続数の
        # 大きいほうを採用
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

# 復元はs,tとも後ろから見ていく
ans = ''
i=ls
j=lt
while i != 0 and j != 0:
    if dp[i][j] == dp[i-1][j]:
        # DP上でsの一個前から更新されてない
        # 即ちs[i-1]は共通列に入ってない
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # 上と同じ論法でtの場合
        j -= 1
    else:
        # 今見ているs[i-1]とt[j-1]が共通になっているとき
        # 答えに採用（s[i-1]は頭につける）
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
c = [A.count(i + 1) for i in range(N)]
ans = [c[i] * (c[i] - 1) // 2 for i in range(N)]
s = sum(ans)

for val in A:
  m = c[val - 1] - 1
  print(s - m)

### FIXED CODE ###

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

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

ans = [c[i] * (c[i] - 1) // 2 for i in range(N)]
s = sum(ans)

for val in A:
  m = c[val - 1] - 1
  print(s - m)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

start = -1
end = A[-1] * F[0]

def check(now):
    cnt = 0
    for a, f in zip(A, F):
        # cnt += max(0, a-now//f)
        eatable = now//f
        if eatable < a:
            cnt += a - eatable
    return cnt <= K
    # if cnt > K:
    #     return False
    # return True

while end > start + 1:
    now = (start + end) // 2
    if check(now):
        end = now
    else:
        start = now

print(end)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

q = [0] * N
start = 0
end = 0
for i in range(N):
    q[i] = A[i] * F[i]
    end = max(end, q[i])

def check(now, K):
    cnt = 0
    for i in range(N):
        if q[i] - now > 0:
            cnt += (q[i] - now + F[i] - 1) // F[i]
            if cnt > K:
                return False
    return True

now = end // 2
while end > start + 1:
    if check(now, K):
        end = now
    else:
        start = now
    now = (start + end) // 2

if check(start, K):
    print(start)
else:
    print(end)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    from collections import defaultdict
    def check(k):
        D=defaultdict(lambda :-1)
        for i in range(n-k+1):
            hash=rh[i:i+k]
            if(D[hash]!=-1):
                if(i-D[hash]>=k): return True
            else:
                D[hash]=i
        return False

    for k in range(n,-1,-1):
        if(check(k)):
            print(k)
            return
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=sys.stdin.readline
def resolve():
    n=int(input())
    s=input()
    dp=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue # i<j
        if s[i]==s[j]:
            dp[i][j]=dp[i+1][j+1]+1
        else:
            dp[i][j]=0
    ans=0
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue
        ans=max(ans,min(j-i,dp[i][j]))
    print(ans)


resolve()
### BUGGY CODE ###

S = input()

N = len(S)
for i in range(2 ** (N + 1)):
    s = bin(i)[2:].zfill(N+1)
    ans = list(S)
    cnt = 0
    for k, j in enumerate(s):
        if j == "1":
            ans.insert(k + cnt, "A")
            cnt += 1
    ans = "".join(ans)
    if ans == "AKIHABARA":
        print("YES")
        exit()

print("NO")




### FIXED CODE ###

S = input()
T = ["AKIHABARA", "KIHABARA", "AKIHBARA", "AKIHABRA", "AKIHABAR",
     "KIHBARA", "KIHABRA", "KIHABAR", "AKIHBRA", "AKIHBAR", "AKIHABR",
     "KIHBRA", "KIHBAR", "KIHABR", "AKIHBR",
     "KIHBR"]
if S in T:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###


import heapq
import collections
N =  int(input())
nums = list(map(int,input().split(" ")))
keta = [0 for _ in range(61)]
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = [1]
MOD = 10 ** 9 + 7
for i in range(60):
    temp = jijou[i] * 2
    temp%= MOD
    jijou.append(temp)

for num in nums:
    s = format(num,"b")
    l = len(s)
    for i in range(0,l):
        keta[i] += int(s[l - i - 1 ])
ans = 0
for j,num in  enumerate(nums[:-1]):
    s = format(num, "b")
    l = len(s)
    for i in range(0,61): #i →  2 ** i 乗 桁目に対応
        if l <= i:
            ans += keta[i] * jijou[i] % MOD
        else:
            if s[l - i - 1 ] == "0":
                ans += keta[i] * jijou[i] % MOD
            else:
#              (N - j + 1) - (keta[i] + 1 ) → 0が経っているところの個数
                ans += ( (N - j + 1) - (keta[i] + 1)  ) * ( jijou[i])  % MOD
                keta[i] -= 1


print(ans % MOD)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
### BUGGY CODE ###

n=int(input())
S=list(input())
ans=0
for i in range(n-2):
  for j in range(i,n-1):
    if S[i]==S[j]:
      continue
    for k in range(j,n):
      if S[j]==S[k] or S[i]==S[k]:
        continue
      if j-i != k-j:
        ans+=1
    continue
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())

nr=s.count('R')
ng=s.count('G')
nb=s.count('B')
ans=nr*ng*nb
cnt=0

for i in range(n-1):
  for j in range(i+1,n):
    k=2*j-i
    if k>=n or k<=j:
      continue
    if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      cnt+=1
print(ans-cnt)
### BUGGY CODE ###

import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]
sset = set(s)
tset = set(t)
for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for letter in sset:
  i = ord(letter) - 97
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    if table[i][len(s)-j-2] < len(s): break
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

if tset - sset:
  print(-1)
  sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

### FIXED CODE ###

import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]
sset = set(s)
tset = set(t)
for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for letter in sset:
  i = ord(letter) - 97
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    if table[i][len(s)-j-2] < len(s): break
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

if tset - sset:
  print(-1)
  sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for i in range(n):
    ans[i]=a.count(i+1)
print(*ans,sep='\n')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for i in range(n-1):
    ans[a[i]-1]+=1
print(*ans,sep='\n')
### BUGGY CODE ###

S=raw_input()
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

for i in range(1,l+1):
	dp2=[0]*13
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*pow(10,l-i,13)+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*pow(10,l-i,13)+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod
	dp=dp2

print dp[5]


### FIXED CODE ###

S=raw_input()
S=S[::-1]
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

keta=1

for i in range(1,l+1):
	dp2=[0]*13
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*keta+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*keta+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod

	dp=dp2
	keta=(keta*10)%13

print dp[5]
### BUGGY CODE ###

#!/usr/bin/python

import sys
import math 

#Input Functions
#===============

input = sys.stdin.readline

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

#===============

def run_test() :
    n = inp()
    a = inlt()
    ans = 1
    zero = False
    invalid = False
    for i in a :
        ans *= i
        if i == 0 : zero = True
        if ans > 1000000000000000000 : invalid = True
    if zero : ans = 0
    elif invalid : ans = -1
    print(ans)

def main() :
	run_test()

if __name__ == '__main__' :
	main()


### FIXED CODE ###

#!/usr/bin/python

import sys
import math 

#Input Functions
#===============

input = sys.stdin.readline

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

#===============

def run_test() :
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)

def main() :
	run_test()

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

N,W=map(int,input().strip().split())
l=[]
for n in range(N):
    l.append(list(map(int,input().strip().split())))

dp=[[0 for w in range(W+1)] for n in range(N+1)]
for n in range(1,N+1):
    for i in range(W+1):
        #各nにつき重みiを超えない最大値を求める
        tmp=l[n-1][0]
        if  tmp+i<=W:
            dp[n][tmp+i]=max(dp[n][tmp+i],dp[n-1][i]+l[n-1][1])
        dp[n][i]=max(dp[n][i],dp[n-1][i])

res=0
for i in range(W+1):
    res=max(res,dp[N][i])

print(res)

### FIXED CODE ###

import numpy as np

def main_():
    N,W=map(int,input().strip().split())
    l=[]
    for n in range(N):
        l.append(list(map(int,input().strip().split())))
    
    dp=np.zeros(W+1,np.int64)

    for n in range(N):
        w=l[n][0]
        v=l[n][1]
        dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
    return dp.max()

if __name__=="__main__":
    print(main_())