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

import sys
input = sys.stdin.readline

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

n=max(A)

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]
#print(table)

lcm=[0]*len(table)
p=[1]*len(table)



for i in range(N):
    a=A[i]
    for j in range(len(table)):
        if a<table[j]:
            break
        if a%p[j]==0:
            a=a//p[j]
            while a%table[j]==0:
                a=a//table[j]
                lcm[j]+=1
                p[j]*=table[j]
                
        
l=1
for j in range(len(table)):
    l*=p[j]
    

ans=0
mod=10**9+7

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



### FIXED CODE ###

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

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

from sys import stdin

L = stdin.readline().rstrip()
inf = 10 ** 9 + 7
ones = 3
if L[-1] == '0':
    ans = 1
else:
    ans = 3

if len(L) == 1:
    print(ans)
    exit()

for i in range(2, len(L) + 1):
    if L[-i] == '1':
        ans = (ones + 2 * ans) % inf
    ones *= 3

print(ans)


### FIXED CODE ###

from sys import stdin

L = stdin.readline().rstrip()
inf = 10 ** 9 + 7
ones = 3
if L[-1] == '0':
    ans = 1
else:
    ans = 3

if len(L) == 1:
    print(ans)
    exit()

for i in range(2, len(L) + 1):
    if L[-i] == '1':
        ans = (ones + 2 * ans) % inf
    ones = (3 * ones) % inf

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [0] * n
for i in range(1, n):
    x=h[i]
    cost[i] = min([cost[j]+abs(x-h[j]) for j in range(max(0, i-k), i)])
print(cost[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
c = [0] * n
for i in range(1, n):
    x=h[i]
    c[i] = min([c[j]+abs(x-h[j]) for j in range(max(0, i-k), i)])
print(c[n-1])
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K and x + y + z == S:
            ans += 1
print(ans)

### FIXED CODE ###

from itertools import  product
K, S = map(int, input().split())
ans = 0
for x,y in product(range(K+1),repeat=2):
    z = S - x - y
    if 0 <= z <= K and x + y + z == S:
        ans += 1
print(ans)
### BUGGY CODE ###

from sys import stdin
lis =[]
#k = int(stdin.readline().rstrip())
lis= stdin.readline().rstrip().split()
k = int(lis[0])
s = int(lis[1])
#s =int(stdin.readline().rstrip())
count = 0

x = 0
y = 0
z = 0

for x in range(s+1):
    y = 0
    for y in range(s+1):
        z = 0
        z = s - x - y
        if x <= k and y <= k and z<= k and 0 <= z:
            count +=1
            #print(x,y,z)

print(count,flush=True)


### FIXED CODE ###

from sys import stdin
lis =[]
#k = int(stdin.readline().rstrip())
lis= stdin.readline().rstrip().split()
k = int(lis[0])
s = int(lis[1])
count = 0
x = 0
y = 0
z = 0
for x in range(k+1):
    y = 0
    for y in range(k+1):
        z = 0
        z = s - x - y
        if z <= k and z >= 0:
                count +=1



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

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

def med(a):
    b = sorted(a)
    num = int((len(b)+1)/2)
    return b[num-1]


for i in range(n):
    temp = x[:]
    temp.remove(x[i])
    print(med(temp))

### FIXED CODE ###

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

a = len(x)
b = sorted(x)
fa = b[int((a/2)-1)]
se = b[int(a/2)]

for i in range(n):
    if x[i] <= fa:
        print(se)
    else:
        print(fa)
### BUGGY CODE ###

from collections import Counter
import copy

def count(dic, key):
    ans = 0
    for i in key:
        d = dic[i]
        ans += d * (d - 1) // 2
    return(ans)

N = int(input())
A = list(map(int, input().split()))
a = dict(Counter(A))
k = list(a.keys())
dic = {}
for i in k:
    a2 = copy.copy(a)
    a2[i] -= 1
    dic[i] = count(a2, k)
for i in range(N):
    print(dic[A[i]])


### FIXED CODE ###

from collections import Counter
import copy

def count(dic, key):
    ans = 0
    for i in key:
        d = dic[i]
        ans += d * (d - 1) // 2
    return(ans)

N = int(input())
A = list(map(int, input().split()))
a = dict(Counter(A))
k = list(a.keys())
m = count(a, k)
dic = {}
for i in k:
    dic[i] = m - a[i] + 1
for i in range(N):
    print(dic[A[i]])
### BUGGY CODE ###

station_num = int(input())

if station_num == 1:
    print(0)
else:
    station_list = [[0, 0, 0] for i in range(station_num)]
    
    for i in range(station_num - 1):
        station_list[i] = input().split()
    # print(station_list)
    
    for i in range(station_num):
        count = int(station_list[i][0]) + int(station_list[i][1])
        now_position = i + 1
        while True:
            if now_position == station_num - 1 or now_position == station_num:
                print(count)
                break
            else:
                while True:
                    if count < int(station_list[now_position][1]):
                        count = int(station_list[now_position][1])
                    elif count % int(station_list[now_position][2]) == 0:
                        count += int(station_list[now_position][0])
                        now_position += 1
                        break
                    else:
                        count += 1

### FIXED CODE ###

station_num = int(input())

if station_num == 1:
    print(0)
else:
    station_list = [[0, 0, 0] for i in range(station_num)]
    
    for i in range(station_num - 1):
        station_list[i] = input().split()
    # print(station_list)
    
    for i in range(station_num):
        count = int(station_list[i][0]) + int(station_list[i][1])
        now_position = i + 1
        while True:
            if now_position == station_num - 1 or now_position == station_num:
                print(count)
                break
            else:
                while True:
                    if count < int(station_list[now_position][1]):
                        count = int(station_list[now_position][1])
                    elif count % int(station_list[now_position][2]) == 0:
                        count += int(station_list[now_position][0])
                        now_position += 1
                        break
                    else:
                        count = count + int(station_list[now_position][2]) - (count % int(station_list[now_position][2]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
if m%2:
  print(-1)
else:
  G = [[] for _ in range(n+1)]
  par = [-1]*(n+1)
  ch = [[] for _ in range(n+1)]
  seen = [False]*(n+1)
  used = set()
  C = [0]*(n+1)
  for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
  
  stack = [1]
  seen[1] = True
  while stack:
    v = stack.pop()
    for nv in G[v]:
      if seen[nv]:
        if par[v] != nv:
          if (min(v, nv), max(v, nv)) not in used:
            used.add((min(v, nv), max(v, nv)))
            print(v, nv)
            C[v] ^= 1
      else:
        seen[nv] = True
        par[nv] = v
        ch[v].append(nv)
        stack.append(nv)
  
  def bottom_up(v):
    for nv in ch[v]:
      bottom_up(nv)
    if v == 1:
      return
    if C[v]:
      C[v] ^= 1
      print(v, par[v])
    else:
      C[par[v]] ^= 1
      print(par[v], v)
      
  bottom_up(1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
if m%2:
  print(-1)
else:
  G = [[] for _ in range(n+1)]
  par = [-1]*(n+1)
  ch = [[] for _ in range(n+1)]
  seen = [False]*(n+1)
  used = set()
  C = [0]*(n+1)
  for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
  
  stack = [1]
  seen[1] = True
  while stack:
    v = stack.pop()
    for nv in G[v]:
      if seen[nv]:
        if par[v] != nv:
          if (min(v, nv), max(v, nv)) not in used:
            used.add((min(v, nv), max(v, nv)))
            print(v, nv)
            C[v] ^= 1
      else:
        seen[nv] = True
        par[nv] = v
        ch[v].append(nv)
        stack.append(nv)
  
  def bottom_up(v):
    for nv in ch[v]:
      bottom_up(nv)
    if v == 1:
      return
    if C[v]:
      C[v] ^= 1
      print(v, par[v])
    else:
      C[par[v]] ^= 1
      print(par[v], v)
      
  bottom_up(1)
### BUGGY CODE ###

K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
        for z in range(0,(K+1)):
            if x + y + z == S:
                tmp += 1
print(tmp)

### FIXED CODE ###

K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
            if 0 <= S - x - y <= K:
                tmp += 1
print(tmp)
### BUGGY CODE ###

A,B,K=map(int,input().split())
for i in range(A,B+1):
  if i <=A+K-1 or i >= B-K+1:
    print(i)

### FIXED CODE ###

A,B,K=map(int,input().split())
ans = set(range(A,min(A+K,B+1))).union(set(range(B,max(A-1,B-K),-1)))

print(*sorted(ans))
### BUGGY CODE ###

n = int(input())
k = [[int(input()),1]]
cou = 1
for i in range(n-1):
    now = int(input())
    flag = False
    for i in range(cou):
        if now == k[i][0] + 1:
            k[i] = [now,k[i][1]+1]
            flag = True
    if not flag:
        k.append([now,1])
        cou += 1
p = 0
for i in range(cou):
    p = max(p,k[i][1])
print(n-p)

### FIXED CODE ###

from bisect import bisect_left,bisect
 
n = int(input())
cou = [0 for i in range(n+1)]
for i in range(n):
    now = int(input())
    cou[now] = cou[now-1] + 1  

print(n-max(cou))
### BUGGY CODE ###

N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 6 + 1

dp = [[10 ** 9 + 1] * V for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(V):
        w, v = items[i]
        if j >= v:
            dp[i + 1][j] = min(dp[i][j - v] + w, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for v in range(V):
    if dp[N][v] <= W:
        ans = v
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 5 + 1

dp = [[10 ** 9 + 1] * V for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(V):
        w, v = items[i]
        if j >= v:
            dp[i + 1][j] = min(dp[i][j - v] + w, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for v in range(V):
    if dp[N][v] <= W:
        ans = v
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ruto = [1]
cnt = 0
saki = a[0]
for i in range(n):
    if cnt != k:
        if saki not in ruto:
            ruto.append(saki)
            cnt += 1
            saki = a[saki-1]
        else:
            where = ruto.index(saki)
            ruto = ruto[where:]
            K = k-where
            ans = K%len(ruto)
            print(ruto[ans])
            break
    else:
        print(ruto[-1])
        break

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ruto = [1]
kako = [0] * (n+1)
kako[1] = 1
saki = a[0]
flag = 0
for _ in range(k):
    if kako[saki] == 1:
        where = ruto.index(saki)
        ruto = ruto[where:]
        ans = (k-where)%len(ruto)
        print(ruto[ans])
        flag = 1
        break
    else:
        ruto.append(saki)
        kako[saki] = 1
        saki = a[saki-1]
if flag == 0:    
    print(ruto[-1])
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
for i in range(len(c)):
  for j in range(len(d)):
    if c[i]+d[j]<=k and i+j>e:
      e=i+j
print(e)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k:
      if i+j>e:
        e=i+j
      f=j
      break
print(e)
### BUGGY CODE ###

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


ans = 0
for i in range(N):
    tmp_sum = 0
    tmp_xor = 0
    for j in range(i, N):
        tmp_sum += A[j]
        tmp_xor ^= A[j]
        if tmp_sum != tmp_xor :
            break
        else:
            ans += 1
print(ans)

### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = list(map(int, input().split()))


tmpxor = 0
tmpadd = 0
ans = 0
minindex = 0
maxindex = 0
for e,i in enumerate(A):
    tmpadd += i
    tmpxor ^= i
    maxindex = e
    if tmpxor != tmpadd:
        while tmpxor != tmpadd and minindex < e:
            tmpxor ^= A[minindex]
            tmpadd -= A[minindex]
            minindex += 1
            # ans += 1
    ans += maxindex - minindex + 1


        # if tmpxor != tmpadd:
        #     maxindex -= 1
    # ans += maxindex - minindex + 1
print(ans)
### BUGGY CODE ###

import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    point = []
    lenq = 0
    constant = 0
    for i in range(Q):
        query = [int(i) for i in line_input()]
        if query[0] == 1:
            constant += query[2]
            point.insert(bisect_left(point, query[1]),query[1])
            lenq += 1
        else:
            j = (lenq - 1)//2
            ans = sum(point[j:]) - sum(point[:j]) + point[j] * (2 * j - lenq) 
            print(point[j], ans + constant)
    return 0
  
if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = [-a], [a]
    heapq.heapify(left)
    heapq.heapify(right)
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            left_upper = -1 * heapq.heappop(left)
            right_lower = heapq.heappop(right)
            if left_upper <= a <= right_lower:
                heapq.heappush(left, -a)
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(right, a)
                heapq.heappush(right, right_lower)
            elif a < left_upper:
                minans += left_upper - a
                heapq.heappush(left, -a)
                heapq.heappush(left, -a)
                heapq.heappush(right, left_upper)
                heapq.heappush(right, right_lower)
            else:
                minans += a - right_lower
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(left, -1 * right_lower)
                heapq.heappush(right, a)
                heapq.heappush(right, a)
        else:
            left_lower = -1 * heapq.heappop(left)
            print(left_lower, minans)
            heapq.heappush(left, -1 * left_lower)
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

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

### FIXED CODE ###

n,q=map(int,input().split())
s=input();a=[0]*2
for i in range(2,n+1):
 a+=[a[i-1]+s[i-2:i].count("AC")]
for _ in range(q):
 l,r=map(int,input().split())
 print(a[r]-a[l])
### BUGGY CODE ###

n=int(input())
s_list=[]

for i in range(n):
  s_elem=list(input())
  s_elem=sorted(s_elem)
  s=''.join(s_elem)
  s_list.append(s)

unq_list=list(set(s_list))
count=0

for j in range(len(unq_list)):
  match_n=s_list.count(unq_list[j])
  count+=sum(range(1, match_n))

print(count)

### FIXED CODE ###

n=int(input())
dic={}

count=0
for i in range(n):
  s_elem=''.join(sorted(list(input())))
  if s_elem in dic:
    count+=dic[s_elem]
    dic[s_elem]+=1
  else:
    dic[s_elem]=1

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

import sys
from bisect import *

def main():
	input = sys.stdin.readline

	N = int(input())
	S = input().strip()
	M = 998244353

	ri = []
	gi = []
	bi = []

	for i, c in enumerate(S):
		if c=='R':
			ri.append(i)
		elif c=='G':
			gi.append(i)
		else:
			bi.append(i)

	si = []
	mi = []
	li = []
	for i in range(N):
		tt = [ri[i],gi[i],bi[i]]
		tt.sort()
		si.append(tt[0])
		mi.append(tt[1])
		li.append(tt[2])

	ans = 1
	for i in range(N):
		st = bisect(si,mi[i])
		lt = bisect(li,mi[i])
		ans *= (st-i)*(i+1-lt)*(i+1)%M

	print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import *

def main():
	input = sys.stdin.readline

	N = int(input())
	S = input().strip()
	M = 998244353

	ri = []
	gi = []
	bi = []

	for i, c in enumerate(S):
		if c=='R':
			ri.append(i)
		elif c=='G':
			gi.append(i)
		else:
			bi.append(i)

	si = []
	mi = []
	li = []
	for i, tt in enumerate(zip(ri,gi,bi)):
		s, m, l = sorted(tt)
		si.append(s)
		mi.append(m)
		li.append(l)

	ans = 1
	for i, mm in enumerate(mi):
		st = bisect(si,mm)
		lt = bisect(li,mm)
		ans = ans*(st-i)*(i+1-lt)*(i+1)
		ans = ans%M

	print(ans)

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

import collections
N = int(input())
D = list(map(int,input().split()))

if D[0] != 0:
    print(0)
    exit()

for i in range(max(D)):
    if i not in D:
        print(0)
        exit()

A = collections.Counter(D)
A = list(A.items())
A.sort()
ans = 1
for i in range(max(D)):
    ans *= A[i][1]**A[i+1][1]
    if ans >= 998244353:
        ans %= 998244353
print(ans)

### FIXED CODE ###

import collections
N = int(input())
D = list(map(int,input().split()))

if D[0] != 0 or 0 in D[1:]:
    print(0)
    exit()

A = collections.Counter(D)
A = list(A.items())
A.sort()

if len(A) != max(D) + 1:
    print(0)
    exit()

ans = 1
for i in range(max(D)):
    ans *= A[i][1]**A[i+1][1]
    if ans >= 998244353:
        ans %= 998244353
print(ans)
### BUGGY CODE ###

import numpy as np 


N,K,Q = map(int,input().split())
arr = np.array([K]*N)

for i in range(Q):
    A = int(input())
    arr[:]-=1
    arr[A-1]+=1
    
for i in range(N):
    if arr[i]>0:
        print("Yes")
    else :
        print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())

li = [0]*N

for _ in range(Q):
    index = int(input())-1
    li[index]+=1


for num in li:
    if K>Q-num:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + n; R = r + n
    s = float("inf")
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    # O(logN)
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

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

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if memo[i][j]>=0:
    return memo[i][j]
  else :
    if i==n:
      memo[i][j]=0
      return memo[i][j]
    elif j<w[i]:
      memo[i][j]=dfs(i+1,j)
      return memo[i][j]
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
      return memo[i][j]
print(dfs(0,W))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])
### BUGGY CODE ###

N = int (input ())
A = [int (x) for x in input().split()]
X = 0
for i in range (N-1):
  for j in range (N-i-1):
    X += A[i]*A[j+i+1]
    X = X%(10**9+7)
print (X)

### FIXED CODE ###

N = int (input ())
A = [int (x) for x in input().split()]
S = sum (A)
X = 0
for i in range (N-1):
  X += A[i]*(S-A[i])
  S -= A[i]
  if X > 10**9+7:
    X = X%(10**9+7)
print (X)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = []

k = len(bin(max(a)))-2
for x in a:
    b.append([int(y) for y in list(bin(x)[2:].zfill(k))])

b = np.array(b)
c = b.T

ans = []
for i in range(k):
    one = sum(c[i])
    if one%2==0:
        pass
    else:
        c[i] = (c[i]+1)%2

d = c.T

for i in range(n):
    ans.append(int(''.join([str(y) for y in d[i]]),2))

print(*ans)

### FIXED CODE ###

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

A = 0
for i in range(n):
    A ^= a[i]

ans = [A^x for x in a]
print(*ans)
### BUGGY CODE ###

n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))


### FIXED CODE ###

n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])