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

n = int(input())
A = list(map(int,input().split()))
lis = []
from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
lc = lcm(A)
for i in range(n):
    lis.append(lc//A[i])
print(sum(lis) % (10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
lc = lcm(A)
for i in range(n):
    ans += lc//A[i]
print(ans % (10**9+7))
### BUGGY CODE ###

count_a = []
pos = 0
while True:
    n, x = list(map(int, input().split()))
    count = 0
    if n == x == 0:
        break
    else:
        for i in range(1, (n+1)):
            for j in range(1, (n+1)):
                for k in range(1, (n+1)):
                    if (i != j) and (j != k) and (i != k):
                        if (i+j+k) == x:
                            count += 1
        count_a.append(int(count/6))
        pos = pos+1

for i  in count_a:
    print(i)


### FIXED CODE ###

count_a = []
pos = 0
while True:
    n, x = list(map(int, input().split()))
    count = 0
    if n == x == 0:
        break
    else:
        for i in range(1, (n+1)):
            for j in range(i+1, (n+1)):
                for k in range(j+1, (n+1)):
                    if (i != j) and (j != k) and (i != k):
                        if (i+j+k) == x:
                            count += 1
        count_a.append(count)
        pos = pos+1

for i  in count_a:
    print(i)
### BUGGY CODE ###

S=list(input())
Q=int(input())
for i in range(Q):
    tmp=list(input().split())
    a=tmp[0]
    #print(tmp)
    if a=='1':
        S.reverse()
    elif a=='2' and tmp[1]=='1':
        S.insert(0,tmp[2])
    else:
        S.append(tmp[2])
print(*S,sep='')

### FIXED CODE ###

S = input()
Q = int(input())
 
a = []
b = []
rev = 0
 
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        a, b = b, a
        rev += 1
    else:
        if q[1] == '1':
            a.append(q[2])
        else:
            b.append(q[2])
if rev % 2 == 1:
    S = S[::-1]
ans = ''.join(a[::-1]) + S + ''.join(b)
print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(s[lr[i][0]-1:lr[i][1]].count('AC'))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
tmp=[0]
l,cnt=0,0
r=2
while r<=n:
  if 'AC' == s[l:r]:
    cnt+=1
    l=r
    tmp.append(cnt)
    tmp.append(cnt)
    r+=2
  else:
    tmp.append(cnt)
    l+=1
    r+=1
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])
### 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()))
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()
LIS = []
LISA = []
LISB = []
LISC = []
for s in range(X):
    for t in range(Y):
        if (s+1)*(t+1) <= 3000:
            for u in range(Z):
                if 3000//(u+1) + 1 > min(s,t):
                    LISA.append(s)
                    LISB.append(t)
                    LISC.append(u)
for i in range(len(LISA)):
    PR = A[LISA[i]]+B[LISB[i]]+C[LISC[i]]
    LIS.append(PR)
LIS.sort()
LIS.reverse()

for i in range(min(len(LIS),K)):
    print(LIS[i])

### FIXED 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()))
A.sort(reverse= True)
B.sort(reverse= True)
C.sort(reverse= True)
LIS = []
for i in range(X):
    INTB = 3000//(i+1)
    for j in range(min(INTB+1,Y)):
        INT = 3000//((i+1)*(j+1))
        for k in range(min(INT+1,Z)):
            SUM = A[i] + B[j] + C[k]
            LIS.append(SUM)
LIS.sort(reverse = True)
for i in range(K):
    print(LIS[i])
### BUGGY CODE ###

a=input()
n=len(a)
if n<5:
    print('NO')
    exit()

for i in range(2**(n+1)):
    s=""
    check=[""]*(n+1)
    for j in range(n+1):
        if ((i>>j)&1):
            check[j]="A"
    for k in range(n+1):
        s+=check[k]
        if k!=n:
            s+=a[k]
    if s=="AKIHABARA":
        print('YES')
        exit()
print('NO')

### FIXED CODE ###

a=input()
n=len(a)
if n<5 or n>10:
    print('NO')
    exit()

for i in range(2**(n+1)):
    s=""
    check=[""]*(n+1)
    for j in range(n+1):
        if ((i>>j)&1):
            check[j]="A"
    for k in range(n+1):
        s+=check[k]
        if k!=n:
            s+=a[k]
    if s=="AKIHABARA":
        print('YES')
        exit()
print('NO')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def S(): return list(sys.stdin.readline())[:-1]
def f():
    s = S()
    t = S()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            if t[i] == s[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])

if __name__ == '__main__':
    f()


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls+1)] for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])
### BUGGY CODE ###

## coding: UTF-8

S = input() #文字列型で受け取る
N = len(S)

remainder = [0] * 2019

for i in range(N):
    #print(S[i:], int(S[i:])%2019)
    remainder[int(S[i:])%2019]+= 1
remainder[0] += 1

answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))


### FIXED CODE ###

## coding: UTF-8

S = input()[::-1] #文字列型で受け取る
N = len(S)
#print(S)

remainder = [0] * 2019
tmp = 0
rad = 1 # *10**(i) % 2019
for i in range(N):
    r = int(S[i])
    tmp += r*rad
    tmp %= 2019
    #print(tmp)
    remainder[tmp] += 1
    rad *= 10
    rad %= 2019

    #print(S[i:], int(S[i:])%2019)
    #remainder[int(S[i:])%2019]+= 1
remainder[0] += 1
#print(-1)



answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))
### BUGGY CODE ###

from collections import deque
from itertools import product

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()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10**12
cost = [[INF] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh = y + dy
        ww = x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m:
            cost[hh][ww] = m
            que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh = y + dy
        ww = x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m + 1:
            cost[hh][ww] = m + 1
            que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

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()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

from itertools import permutations

N,M,R=map(int,input().split())
r=[int(x) for x in input().split()]
INF=float('inf')
d=[[INF for x in range(N)] for y in range(N)]
for i in range(N):
  d[i][i]=0

for i in range(M):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

for i in range(N):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)


### FIXED CODE ###

from itertools import permutations

N,M,R=map(int,input().split())
r=[int(x) for x in input().split()]

INF=float('inf')
d=[[INF for x in range(N)] for y in range(N)]

for i in range(M):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

for i in range(N):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = list(map(int, list(input())))

print(len(set(combinations(S,3))))

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

ans = set()
for i in range(10):
  for j in range(10):
    for k in range(10):
      iflg = False
      jflg = False
      for s in S:
        if not iflg and s == i:
          iflg = True
        elif (not jflg) and iflg and s == j:
          jflg = True
          continue
        elif iflg and jflg and s == k:
          ans.add((i,j,k))
          break
print(len(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]
A = [[0]*c for _ in range(3)]
for i in range(n):
  for j in range(n):
    x = C[i][j] - 1
    r = (i+j)%3
    for y in range(c):
      A[r][y] += D[x][y]
ans = float("inf")
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i == j or j == k or k == i:
        continue
      temp = A[0][i] + A[1][j] + A[2][k]
      ans = min(ans, temp)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]
A = [[0]*c for _ in range(3)]
for i in range(n):
  for j in range(n):
    x = C[i][j] - 1
    r = (i+j)%3
    for y in range(c):
      A[r][y] += D[x][y]
ans = float("inf")
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i == j or j == k or k == i:
        continue
      temp = A[0][i] + A[1][j] + A[2][k]
      ans = min(ans, temp)
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if i * j >= N:
            break
#         print(1, j)
        ans += 1
print(ans)



### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    cnt = (N-1) // i
#     for j in range(1, cnt+1):
#         if i * j >= N:
#             break
#         print(1, j)
    ans += cnt
print(ans)
### BUGGY CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            if p == n-1:
                break
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

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

import numpy as np

n,X = map(int,input().split())
xs = np.array(list(map(int,input().split())))
cumsumx =np.insert(np.cumsum(xs),0,0)

def energy(k):
    nok = n//k
    acm = (n+k)*X + 2*(cumsumx[-1] - cumsumx[-k-1])+cumsumx[-1]
    acm += 2*sum([cumsumx[-1-k*(i-1)] for i in range(1,nok+2)])
    return(acm)

ans = -1
for j in range (1,min(n//2+4,n+1)):
    tmp = energy(j)
    if tmp < ans or ans == -1:
        ans =tmp

print(ans)





### FIXED CODE ###

import numpy as np
 
n,X = map(int,input().split())
xs = np.array(list(map(int,input().split())))
cumsumx =np.insert(np.cumsum(xs),0,0)
 
cut = np.int_(3000000000000000000)
 
def cutsum(array):
    acm = np.int_(0)
    for i in array:
        if acm <= cut:
            acm += i
        else:
            acm = cut
            break
    return(acm)
 
def energy(k):
    nok = n//k
    offset = (n+k)*X
    acm = (n+k)*X + 3*cumsumx[-1] - 2*cumsumx[-k-1]
    acm += 2*cutsum(cumsumx[::-k])
    return(acm)
 
ans = (n+1)*X+2*cutsum(cumsumx)+3*cumsumx[-1]-2*cumsumx[-2]
for j in range (2,min(n//2+4,n+1)):
    tmp = energy(j)
    if tmp < ans:
        ans =tmp
 
print(ans)
### BUGGY CODE ###

import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
for i in range(N):#最大公倍数
    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

for i in range(N):
    ans+=min_bai//A[i]
    ans=ans%mod

print(ans)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
### BUGGY CODE ###

# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]

queue,new_queue = [],[]

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))
            
def darker(i,j):
    if (i in h) and (j in w) and A[i][j]=='.':
        A[i][j]='#'
        new_queue.append((i,j))

ans = 0

while True:
    new_queue = []
    for i,j in queue:
        darker(i-1,j)
        darker(i+1,j)
        darker(i,j-1)
        darker(i,j+1)
    if new_queue==[]:
        break
    ans += 1
    queue = new_queue 

print(ans)

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
de = deque()
for n in range(N):
    com = input().split()
    if com[0] == "insert":
        de.appendleft(int(com[1]))
    elif com[0] == "delete":
        try:
            de.remove(int(com[1]))
        except:
            pass
    elif com[0] == "deleteFirst":
        de.popleft()
    else:
        de.pop()
print(*de)
    
    



### FIXED CODE ###

from collections import deque
N = int(input())
de = deque()
for n in range(N):
    com = input().split()
    if com[0] == "insert":
        de.appendleft(com[1])
    elif com[0] == "delete":
        try:
            de.remove(com[1])
        except:
            pass
    elif com[0] == "deleteFirst":
        de.popleft()
    else:
        de.pop()
print(*de)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC136 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

s = input()
n = len(s)
x = []
for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L':
        x.append(i)

ans = [0]*n
for i in range(n):
    if s[i] == 'R':
        for j in x:
            if j >= i:
                tmp = j
                break
        #print((10**100 - (tmp-i)) % 2)
        ans[(10**100 - (tmp-i)) % 2 + tmp] += 1
    else:
        for j in x[::-1]:
            if j <= i:
                tmp = j
                break
        #print((10**100 - (i-tmp+1)) % 2)
        ans[(10**100 - (i-tmp)) % 2 + tmp] += 1
print(*ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC136 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

s = input()
n = len(s)
x = []
for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L':
        x.append(i)

ans = [0]*n
for i in range(n):
    if s[i] == 'R':
        tmp = bisect.bisect_left(x,i)
        tmp = x[tmp]
        #print((10**100 - (tmp-i)) % 2)
        ans[(10**100 - (tmp-i)) % 2 + tmp] += 1
    else:
        tmp = bisect.bisect_right(x,i)
        tmp = x[tmp-1]
        #print((10**100 - (i-tmp+1)) % 2)
        ans[(10**100 - (i-tmp)) % 2 + tmp] += 1
print(*ans)
### BUGGY CODE ###

N = int(input())

answer = 0
for c in range(1, N):
    target = N - c
    count = 0
    for i in range(1, target+1):
        if target % i == 0:
            count += 1
    answer += count

print(answer)


### FIXED CODE ###

N = int(input())

answer = 0
for a in range(1, N):
    answer += (N-1) // a

print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,W = map(int, input().split())
iw,v = map(int, input().split())
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = map(int,input().split())
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(n+1):
    if i*iw>W:
        break
    for j in range(n-i+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(n-(i+j)+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(n-(i+j+k)+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,W = map(int, input().split())
iw,v = map(int, input().split())
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = map(int,input().split())
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(min(n,len(d[0]))+1):
    if i*iw>W:
        break
    for j in range(min(n-i,len(d[1]))+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(min(n-(i+j),len(d[2]))+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(min(n-(i+j+k),len(d[3]))+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)
### BUGGY CODE ###

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

black, white = [], 0
for y, line in enumerate(STAGE):
	for x, cell in enumerate(line):
		if "#" == cell:
			black += [(y, x)]
		else:
			white += 1

stage = STAGE
ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

def get_next(p, d):
	n = (p[0] + d[0], p[1] + d[1])
	if 0 <= n[0] < H and 0 <= n[1] < W:
		return n
	return None

def set_val(p, v):
	global stage
	stage[p[0]][p[1]] = v

def get_val(p):
	return stage[p[0]][p[1]]

count = 0
while white:
	count += 1
	next_black = []
	for b in black:
		for d in ds:
			n = get_next(b, d)
			if n:
				v = get_val(n)
				if "." == v:
					white -= 1
					set_val(n, "#")
					next_black += [n]
	black = next_black

print(count)


### FIXED CODE ###

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

black, white = [], 0
for y, line in enumerate(STAGE):
	for x, cell in enumerate(line):
		if "#" == cell:
			black += [(y, x)]
		else:
			white += 1

stage = STAGE
ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

def get_next(p, d):
	n = (p[0] + d[0], p[1] + d[1])
	if 0 <= n[0] < H and 0 <= n[1] < W:
		return n
	return None

def set_val(p, v):
	global stage
	stage[p[0]][p[1]] = v

def get_val(p):
	return stage[p[0]][p[1]]

count = 0
while white:
	count += 1
	next_black = []
	for b in black:
		for d in ds:
			n = get_next(b, d)
			if n:
				v = get_val(n)
				if "." == v:
					white -= 1
					set_val(n, "#")
					next_black += [n]
	black = next_black

print(count)