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

characteristic=10**9+7
def plus(input1,input2):
    return (input1+input2)%characteristic
def minus(input1,input2):
    return (input1-input2)%characteristic
def times(input1,input2):
    return (input1*input2)%characteristic
def exponen(input1,input2):
    binaryl=list(str(bin(input2))[2:])
    binarysize=len(binaryl)
    binarylist=[int(binaryl[binarysize-1-i]) for i in range(binarysize)]
    modlist=[0 for i in range(binarysize)]
    modlist[0]=input1
    for i in range(1,binarysize):
        modlist[i]=times(modlist[i-1],modlist[i-1])
    answer=1
    for i in range(binarysize):
        if binarylist[i]==1:
            answer=times(answer,modlist[i])
    return answer
def divide(input1,input2):
    return times(input1,exponen(input2,characteristic-2))
N=int(input())
Fact=[1 for i in range(N+1)]
Finv=[1 for i in range(N+1)]
for i in range(1,N+1):
    Fact[i]=times(Fact[i-1],i)
    Finv[i]=divide(Finv[i-1],i)
ans=0
def C(A,B):
    return times(Fact[A],times(Finv[B],Finv[A-B]))
SGL=[0 for i in range(N)]
for K in range(N):
    if 2*K-N<0:
        continue
    SGL[K]=times(times(Fact[K],Fact[K-1]),Finv[2*K-N])
for K in range(1,N):
    ans=plus(ans,times(SGL[K]-SGL[K-1],K))
print(ans)


### FIXED CODE ###

P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
N=int(input())
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
    Finv[i+1]=(Finv[i]*inv(i+1))%P
SGN=[0 for i in range(N)]
ans=0
for k in range(N):
    if 2*k-N>=0:
        SGN[k]=(((Fact[k-1]*Fact[k])%P)*Finv[2*k-N])%P
        ans=(ans+k*(SGN[k]-SGN[k-1]))%P
print(ans)
### BUGGY CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=list(input())
  moji.sort()
  moji=''.join(moji)
  A.append(moji)
A.sort()
N=0
for i in range(n):
  a=A[i]
  for s in range(i+1,n):
    b=A[s]
    if a==b:
      N+=1
    else:
      break
print(N)

### FIXED CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=list(input())
  moji.sort()
  moji=''.join(moji)
  A.append(moji)
A.sort()
N=0
SUM=0
i=0
while True:
  if i==n-1:
    SUM=SUM+int(0.5*N*(N+1))
    break
  a=A[i]
  for s in range(i+1,n,1):
    b=A[s]
    if a==b:
      N+=1
      i+=1
    else:
      SUM=SUM+int(0.5*N*(N+1))
      N=0
      i=s
      break
print(SUM)
### BUGGY CODE ###

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

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
memo = {}
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    key = (depth, index, pt, str(left))
    if key in memo:
        return memo[key]
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    memo[key] = probably_ans
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))
### BUGGY CODE ###

N = int(input())
s = list(input())
L = [[], [], []]
for i in range(N):
  if s[i] == 'R':
    L[0].append(i)
  elif s[i] == 'G':
    L[1].append(i)
  else:
    L[2].append(i)
l = [len(L[i]) for i in range(3)]
ans = l[0] * l[1] * l[2]
bb = []
if l[0] <= l[1] <= l[2]:
    bb = [0, 1, 2]
elif l[0] <= l[2] <= l[1]:
    bb = [0, 2, 1]
elif l[1] <= l[0] <= l[2]:
    bb = [1, 0, 2]
elif l[1] <= l[2] <= l[0]:
    bb = [1, 2, 0]
elif l[2] <= l[0] <= l[1]:
    bb = [2, 0, 1]
elif l[2] <= l[1] <= l[0]:
    bb = [2, 1, 0]
for i in L[bb[0]]:
  for j in L[bb[1]]:
    p = 2 * i - j
    q = 2 * j - i
    r = (i + j) / 2
    for k in L[bb[2]]:
      if k > max(p, q, r):
        break
      if k == p:
        ans = ans - 1
      if k == q:
        ans = ans - 1
      if k == r:
        ans = ans - 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
R = []
G = []
for i in range(N):
  if S[i] == "R":
    R.append(i)
  elif S[i] == "G":
    G.append(i)
r = len(R)
g = len(G)
ans = r * g * (N - r - g)
for i in R:
  for j in G:
    a = 2 * i - j
    b = 2 * j - i
    c = i + j
    if 0 <= a < N and S[a] == "B":
      ans -= 1
    if 0 <= b < N and S[b] == "B":
      ans -= 1
    if c % 2 == 0 and S[c//2] == "B":
      ans -= 1
print(ans)
### BUGGY CODE ###

import math
def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
strings = []
anagrams_num = []
for i in range(N):
  string = ''.join(sorted(input()))
  try:
    anagram_index = strings.index(string)
    anagrams_num[anagram_index] += 1
  except:
    strings.append(string)
    anagrams_num.append(0)

ans = 0
for anagram_num in anagrams_num:
  if anagram_num > 0:
    ans += int(cmb(anagram_num+1,2)) 
print(ans)

### FIXED CODE ###

import math
def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
anagrams = {}
for i in range(N):
  string = ''.join(sorted(input()))
  if string in anagrams:
    anagrams[string] += 1
  else:
    anagrams[string] = 0

ans = 0
for anagram_num in anagrams.values():
  if anagram_num> 0:
    ans += int(cmb(anagram_num+1,2)) 
print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
q = deque()
one_time = deque()
q.append([ch, cw])
while len(q) > 0:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while len(one_time) > 0:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

### FIXED CODE ###

from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()
for i in range(q):
    l, r = map(int, input().split())
    print(S[l-1:r].count("AC"))

### FIXED CODE ###

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

S = list(input())

A = [0]

for i in range(1, n+1):
    # if S[i-1:i]:
    if S[i-2:i] == ['A', 'C']:
        A.append(A[-1] + 1)
    else: 
        A.append(A[-1])
# print(A[1:])
A = A[1:]
for i in range(q):
    a, b = map(int, input().split())
    print(A[b-1] - A[a-1])
### BUGGY CODE ###

import math
from functools import reduce

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

n = int(input())
t = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            t += gcd(i, j, k)
print(t)

### FIXED CODE ###

import math
from functools import reduce

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

n = int(input())
t = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            t += gcd(i, j, k)
print(t)
### BUGGY CODE ###

N = int(input())
L = input().split()
Li = []
for i in L:
  Li.append(int(i))
Li.sort()
ret = 0
for i in range(2, N):
  for j in range(1,i):
    for k in range(0,j):
      if Li[j]+Li[k] > Li[i]:
        ret += j-k
#        print(i)
#        print(j)
#        print(k)
        break
      else:
        pass
print(ret)

### FIXED CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L,L[i]+L[j]-1)-j-1
print(ret)
### BUGGY CODE ###

nkc = list(map(int, input().split()))
s = input()
num = [0 for i in range(nkc[0])]
ok = [i for i in range(nkc[0]) if s[i]=='o']

def next_day(f_day, ol, c):
    nk = []
    for x in ol:
        if x-f_day >= c+1:
            nk.append(x)
    return nk

avail_dict = dict()
for i in range(len(ok)):
    avail_dict[ok[i]] = next_day(ok[i], ok[i:], nkc[2])

def workday_search(nk_list, avail_dict, depth, k):
    if len(nk_list) == 0:
        return False
    elif depth+1 == k:
        return nk_list
    else:
        days = []
        for x in nk_list:
            tmp = workday_search(avail_dict.get(x), avail_dict, depth+1, k)
            if tmp:
                for data in tmp:
                    if type(data) == int:
                        days.append([x, data])
                    else:
                        y = [x]
                        y.extend(data)
                        days.append(y)
        return days

last_day = ok[-1:][0]
workdays = workday_search([x for x in ok if (last_day-x+1) >= (nkc[1]+nkc[2]*(nkc[1]-1))], avail_dict, 0, nkc[1])

for res in workdays:
    if type(res) == int:
        num[res] += 1
    else:
        for i in res:
            num[i] += 1

for i in range(nkc[0]):
    if num[i] == len(workdays):
        print(i+1)

### FIXED CODE ###

nkc = list(map(int, input().split()))
s = input()
ok = [i for i in range(nkc[0]) if s[i]=='o']

L = []
today = -1000000
for x in ok:
    if x-today >= nkc[2]+1:
        today = x
        L.append(x)
    if len(L) == nkc[1]:
        break

R = []
today = 1000000
ok.reverse()
for x in ok:
    if today-x >= nkc[2]+1:
        today = x
        R.append(x)
    if len(R) == nkc[1]:
        break

R.reverse()
for i in range(nkc[1]):
    if L[i] == R[i]:
        print(L[i]+1)
### BUGGY CODE ###

import fractions
k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            f = fractions.gcd(i, j)
            ans += fractions.gcd(f, l)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            f = gcd(i, j)
            ans += gcd(f, l)
print(ans)
### BUGGY CODE ###

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

R=[0]*N
G=[0]*N
B=[0]*N

for i in range(N):
    if S[i]=='R':
        R[i]=1
    elif S[i]=='G':
        G[i]=1
    elif S[i]=='B':
        B[i]=1
r=sum(R)
g=sum(G)
b=sum(B)

ans=r*g*b
dib=0

for i in range(N-2):
    for j in range(i+1,N-1):
            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)


### 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 ###

N = int(input())
As = map(int, input().split())
result = 1
 
for a in As:
  result *= a
 
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
 
if 0 in A:
  print(0)
  exit()

for a in A:
  result *= a
  if result > 10**18:
    print(-1)
    exit()

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

n = int(input())
al = list(map(int, input().split()))
mod = 10**9+7
ans = 0

for i in range(n):
    for j in range(n):
        if i != j:
            ans += al[i]*al[j]

print((ans//2)%mod)

### FIXED CODE ###

n = int(input())
al = list(map(int, input().split()))
mod = 10**9+7
ans = sum(al)**2

for ai in al:
    ans -= ai**2

print((ans//2)%mod)
### BUGGY CODE ###



from collections import defaultdict

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

for i in range(N):
    A = list(map(int, input().split()))

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = []
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    cnt_today = 0
    
    for l,h in match_today:
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = []


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

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

import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]    


    token = lines[0].split(" ")
    n = int(token[0])
    
    a = [int(e) for e in lines[1].split(" ")]
    
    return (n, a)


def solve(n, a):


    current_max = -1
    result = "Yes"
    reduced_all = set()
    for i in range(n):

        if a[i] >= current_max:
            current_max = a[i]
        else:
            reduced_tmp = set()
            for j in range(i):
                if a[j] == current_max:
                    if j in reduced_all:
                        result = "No"
                        break
                    else:
                        reduced_tmp.add(j)

            if result == "No":
                break

            current_max = current_max - 1
            for j in reduced_tmp:
                reduced_all.add(j)
                a[j] = a[j] - 1
                if a[j] > a[i]:
                    result = "No"
                    break            

            if result == "No":
                break

    return result


def main():
    # 出力

    print("%s" % solve(*parse_input()))


if __name__ == '__main__':

    main()


### FIXED CODE ###

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

import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]    


    token = lines[0].split(" ")
    n = int(token[0])
    
    a = [int(e) for e in lines[1].split(" ")]
    
    return (n, a)


def solve(n, a):


    current_max = -1
    result = "Yes"
    reduced_all = set()
    last_j = 0
    for i in range(n):

        if a[i] >= current_max:
            current_max = a[i]
        else:
            reduced_tmp = set()
            for j in range(last_j, i):
                if a[j] == current_max:
                    if j in reduced_all:
                        result = "No"
                        break
                    else:
                        reduced_tmp.add(j)

            if result == "No":
                break

            current_max = current_max - 1
            for j in reduced_tmp:
                reduced_all.add(j)
                a[j] = a[j] - 1
                if a[j] > a[i]:
                    result = "No"
                    break
                else:
                    last_j = max(j, last_j)


            if result == "No":
                break

    return result


def main():
    # 出力

    print("%s" % solve(*parse_input()))


if __name__ == '__main__':

    main()
### BUGGY CODE ###

import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, sv in enumerate(C[:-item_w]):
            V = [v + item_v * j for j, v in enumerate(C[i + item_w::item_w], start=1)]
            C[i] = max(V + [sv])
    print(C[0])

solve()

### FIXED CODE ###

import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C, C[item_w:]), start=item_w):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[W])

solve()