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

INT_MIN = 0

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MIN] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INT_MIN
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
MAX_Ai = 3*10**5+1
n, dat = init(MAX_Ai)
for ai in A:
    max_len = query(max(ai-K, 0), min(ai+K+1, MAX_Ai), 0, 0, n)
    update(ai, max_len+1)
ans = query(0, MAX_Ai, 0, 0, n)
print(ans)

### FIXED CODE ###

INT_MIN = 0

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MIN] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

def query(l, r, n):
    res = INT_MIN
    l += n
    r += n
    while l < r:
        if l & 1:
            res = max(res, dat[l-1])
            l += 1
        if r & 1:
            r -= 1
            res = max(res, dat[r-1])
        l >>= 1
        r >>= 1
    return res

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
MAX_Ai = 3*10**5+1
n, dat = init(MAX_Ai)

for ai in A:
    max_len = query(max(ai-K, 0), min(ai+K+1, MAX_Ai), n)
    update(ai, max_len+1)
ans = query(0, MAX_Ai, n)
print(ans)
### BUGGY CODE ###

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(first_word) == get_counter(second_word)

N = int(input())

S = [0 for i in range(N)]

for i in range(N):
  S[i] = input()
  
ans = 0

for i in range(N):
  for j in range(i+1,N):
    if verify_anagrams(S[i],S[j]) == True:
      ans += 1

print(ans)

### FIXED CODE ###

import collections
def resolve():
    N = int(input())
    S = [input() for i in range(N)]
    ans = 0

    for i in range(N):
        S[i]=str(sorted(S[i]))
    c = collections.Counter(S)
    for i in c.values():
        for j in range(1,i):
            ans += j
    print(ans)
    
resolve()
### BUGGY CODE ###

"""
蟻本p37にスタート・ゴールの座標が決まっている場合のコードがある
この問題ではスタート・ゴールの座標が決まっていないので以下のように改変する
"""
h, w = list(map(int, input().split()))
field = [input() for _ in range(h)]

INF = 10**8
d = [[0]*w for i in range(h)] # 各点までの最短距離の配列
dx = [1,0,-1,0]; dy = [0,1,0,-1] # 移動4方向のベクトル

# (sx, sy)から(gx, gy)への最短距離を求める
# たどり着けないとINF
import queue

def bfs(sx, sy, gx, gy):
    que = queue.Queue()
    # 全ての点をINFで初期化
    for i in range(h):
        for j in range(w):
            d[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d[sx][sy] = 0
    
    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy: break
        
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を(nx, ny)とする
            nx = p[0] + dx[i]; ny = p[1] + dy[i]

            # 移動が可能かの判定と既に訪れたことがあるかの判定(d[nx][ny] != INF なら訪れたことあり)
            if 0 <= nx and nx < h and 0 <= ny and ny < w and field[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
            
    return d[gx][gy]

# この問題ではスタート・ゴールの位置が決まっていないので取り得る位置の組み合わせを列挙する
from itertools import combinations

sg_candidates = []
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            sg_candidates.append((i,j))
sg_pairs = combinations(sg_candidates, 2)

ans = 0
for s,g in sg_pairs:
    res = bfs(s[0],s[1],g[0],g[1])
    ans = max(res, ans)

print(ans)

### FIXED CODE ###

h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]

INF = 1001001001
di = [-1,0,1,0]
dj = [0,-1,0,1]
ans = 0

def update(i, j, x):
    if dist[i][j] != INF: return
    dist[i][j] = x
    que.put([i,j])

import queue

# スタートの座標全てのパターンについて距離を計算
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#': continue
        dist = [[INF]*w for i in range(h)]
        que = queue.Queue()
        update(si, sj, 0)
        while que.qsize():
            p = que.get()
            i = p[0]; j = p[1]
            for drc in range(4):
                ni = i+di[drc]; nj = j+dj[drc]
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if s[ni][nj] == '#': continue
                update(ni, nj, dist[i][j]+1)
        # ゴールの座標全てのパターンについて距離を更新
        for i in range(h):
            for j in range(w):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])

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

def buble_sort(list,ans):
    i=len(list)
    while(i>1):
        for j in range(i-1):
            if(list[j]<list[j+1]):
                list[j],list[j+1]=list[j+1],list[j]
            elif(list[j]==list[j+1]):
                ans="NO"
                return ans
            else:
                pass
        i-=1
    return ans

N=int(input())
A=list(map(int,input().split()))
ans="YES"
ans=buble_sort(A,ans)
print(ans)

### FIXED CODE ###

def quick_sort(list):
    stand=list[0]
    over=[]
    same=[]
    under=[]
    for i in list:
        if(i>stand):
            over.append(i)
        elif(i<stand):
            under.append(i)
        else:
            same.append(i)
    if(len(over)>1):
        over=quick_sort(over)
    else:
        pass
    if(len(under)>1):
        under=quick_sort(under)
    else:
        pass

    return over+same+under

N=int(input())
A=list(map(int,input().split()))
A=quick_sort(A)
ans="YES"
if(len(A)>1):
    for i in range(len(A)):
        if(A[i-1]==A[i]):
            ans="NO"
            break
        else:
            pass
else:
    pass
print(ans)
### BUGGY CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([[i, j] for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
for a in A[1:]:
    for i,b in enumerate(B):
        if b<a:
            B[i] = a
            break
    else:
        B.append(a)
print(len(B))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1

for a in A[1:]:
    l = 0
    r = ans - 1
    if B[0]<a:r=0
    while l+1<r:
        i = (l+r)//2
        if B[i] < a:
            r = i
        else:
            l = i
    if B[r]<a:B[r] = a
    else:
        B.append(a)
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
result = 0
for i in range(n):
    h = True
    for x in range(n):
        for y in range(x, n):
            if s[(x+i)%n][y]==s[(y+i)%n][x]:
                continue
            else:
                h = False
                break
        if h==False:
            break
    if h:
        result += 1
print(result*n)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
result = 0
for i in range(n):
    h = True
    for x in range(n):
        if all(s[(x+i)%n][y]==s[(y+i)%n][x] for y in range(x, n)):
            continue
        else:
            h = False
            break
    if h:
        result += 1
print(result*n)
### BUGGY CODE ###

N=int(input())
inp=[]
for _ in range(N):
    inp.append(int(input()))
inp.sort(reverse=True)
    
data=[inp[0]]

for t in range(1,N):
    
    if t%2:
        a=inp[-(t//2+1)]
    else:
        a=inp[t//2]
    
    max_num=abs(data[0]-a)
    max_ind=0
     
    if max_num<abs(data[-1]-a):
        max_num=abs(data[-1]-a)
        max_ind=len(data)
         
    for i in range(1,len(data)):
        temp=abs(data[i]-a)+abs(data[i-1]-a)-abs(data[i]-data[i-1])
        if temp > max_num:
            max_num=temp
            max_ind=i
            
    data.insert(max_ind,a)
    
ans=0

for i in range(N-1):
    ans += abs(data[i+1]-data[i])
    
print(ans)

### FIXED CODE ###

N=int(input())
inp=[]
for _ in range(N):
    inp.append(int(input()))
inp.sort()

if N%2:
    
    m1=inp[:(N//2+1)]
    M1=inp[(N//2+1):]
    
    m2=inp[:N//2]
    M2=inp[N//2:]
    
    a1=sum(M1)*2-sum(m1)*2+m1[-1]+m1[-2]
    a2=sum(M2)*2-sum(m2)*2-M2[0]-M2[1]
    
    print(max(a1,a2))
    
else:
    
    m=inp[:N//2]
    M=inp[N//2:]
    
    a=sum(M)*2-sum(m)*2+m[-1]-M[0]
    
    print(a)
### BUGGY CODE ###

#D
import sys
k = int(input())
count = 0
i=1
while count != k:
    a = str(i)
    b=True
    for j in range(len(a)-1):
        if int(a[j + 1]) == int(a[j]) + 1 or int(a[j]) == int(a[j + 1]) + 1 or int(a[j]) == int(a[j + 1]):
            pass
        else:
            b=False
    if b:
        count += 1
    i+=1
print(i-1)

### FIXED CODE ###

#D
from collections import deque
import sys
k=int(input())
que = deque()
count=0
for i in range(1, 10):  #1~9まで
    que.append(i)
    count += 1
    if count == k:
        print(que.pop())
        sys.exit()
# print(que)
# print(count)
while True:
    tmp = que.popleft()  #データを左から取り出す
    tmp = tmp * 10 + tmp % 10  #中心整数を求める 中心整数＋下一桁
    if tmp % 10 != 0:  #下一桁目が0でない場合
        que.append(tmp- 1)
        count += 1
        # print(count)
        if count == k:
            break
    que.append(tmp)
    count += 1
    # print(count)
    if count == k:
        break
    if tmp % 10 != 9:
        que.append(tmp + 1)
        count += 1
        # print(count)
        if count == k:
            break
    # print(que)
print(que.pop())
### BUGGY CODE ###

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

if n < abs(n-k):
    print(n)

else:
    while n > 0:
        n -= k
    print(min(abs(n), n+k))

### FIXED CODE ###

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

print(min(n % k, k - n % k))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2 * 10 ** 5)


def dfs(v, p):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve():
    if n == 1:
        return True

    d, v = dfs(0, -1)
    d, v = dfs(v, -1)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve() else 'Second')


### FIXED CODE ###

import sys

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


def dfs(v, p, links):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v, links)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve(n, links):
    if n == 1:
        return True

    d, v = dfs(0, -1, links)
    d, v = dfs(v, -1, links)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve(n, links) else 'Second')
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = []
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw.append(str(h-1)+"_"+str(w-1))
mh = max(Hsum)
mw = max(Wsum)
hmax_ind = list(map(lambda x: True if x == mh else False, Hsum))
hmax_ind = list(itertools.compress(range(len(Hsum)), hmax_ind))
wmax_ind = list(map(lambda x: True if x == mw else False, Wsum))
wmax_ind = list(itertools.compress(range(len(Wsum)), wmax_ind))
 
res = []
for n1, n2 in itertools.product(hmax_ind, wmax_ind):
  res.append(str(n1)+"_"+str(n2))
 
if len(set(res).intersection(set(hw))) == len(res):
  print(mh + mw-1)
else:
  print(mh + mw)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = set()
for m in range(M):
  h, w = map(lambda x: int(x) - 1, input().split())
  Hsum[h] += 1
  Wsum[w] += 1
  hw.add((h, w))

mh = max(Hsum)
mw = max(Wsum)
hidx = [i for i, _ in enumerate(Hsum) if _ == mh]
widx = [i for i, _ in enumerate(Wsum) if _ == mw]
 
if len(hidx) * len(widx) > M:
  print(mh + mw)
else:
  fi_flg = False
  for h in hidx:
    for w in widx:
      if (h, w) not in hw:
        print(mh + mw)
        fi_flg = True
        break
    if fi_flg:
      break
  if fi_flg is False:
    print(mh + mw - 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
mod=10**9+7
for k in range(60):
    count=sum([int(bin(a)[2:].zfill(60)[k]) for a in A])
    ans+=count*(N-count)*(2**(60-k-1))
print(ans%mod)


### FIXED CODE ###

N=int(input())
A=[format(i,'060b') for i in map(int,input().split())]
ans=0
mod=10**9+7
for k in range(60):
    count=[a[60-1-k] for a in A].count('0')
    ans+=count*(N-count)*(2**k)%mod
print(ans%mod)
### BUGGY CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
nums=[i for i in range(n)]
for num in nums:
  s=l[:num]+l[num+1:]
  print(max(s))
  

### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=sorted(l)
p=s[-1]
q=s[-2]
for i in range(n):
  if l[i]==p:
    print(q)
  else:
    print(p)
### BUGGY CODE ###

N = int(input())

def solve(N):
    for i in range(1,N+1):
        ans = 0
        flag = 0
        for x in range(1,int(N**0.5)+1):
            for y in range(x,int(N**0.5)+1):
                for z in range(y,int(N**0.5)+1):
                    if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                        if x == y and y == z:
                            ans = 1
                            flag = 1
                            break
                        else:
                            ans = 3
                            flag = 1
                            break
                if flag == 1:
                    break
            if flag == 1:
                break
        if flag == 1:
            print(ans)
        else:
            print(0)
        
solve(N)

### FIXED CODE ###

N = int(input())

from collections import deque
tmp = []
tmp = deque(tmp)
num = [0]*(10**4*7)
for i in range(1,10**2+1):
    tmp.append(i**2)

for x in tmp:
    xx = int(x**0.5)
    for y in tmp:
        yy = int(y**0.5)
        for z in tmp:
            zz = int(z**0.5)
            ans = x + y + z + xx*yy + yy*zz + zz*xx
            num[ans] += 1
            
for i in range(1,N+1):
    print(num[i])
### BUGGY CODE ###

n = int(input())
Al = list(map(int, input().split()))
for i in range(n):
    print(Al.count(i+1))

### FIXED CODE ###

from collections import Counter
n = int(input())
Al = list(input().split())
cdict = Counter(Al)
for i in range(n):
    print(cdict[str(i+1)])
### BUGGY CODE ###

n, a, b = [int(i) for i in input().split(" ")]

def p2l(x):
    l = []
    for i in range(0, n):
        l = [x % 2] + l
        x = x // 2
    return l

def l2p(x):
    return sum([x[i] * 2**(len(x) - i - 1) for i in range(0, len(x))])

al = p2l(a)
bl = p2l(b)

def gray(a, b):
    if len(a) == 1:
        return [a, b]
    
    for i in range(0, len(a)):
        if a[i] != b[i]:
            break
    ah = a[i]
    bh = b[i]
    del a[i]
    del b[i]
    
    c = [1 - a[0]] + a[1:]
    g1 = gray(a[:], c[:])
    g2 = gray(c[:], b[:])
    g1 = [h[0:i] + [ah] + h[i:] for h in g1]
    g2 = [h[0:i] + [bh] + h[i:] for h in g2]
    return g1 + g2

if sum(al) % 2 != sum(bl) % 2:
    print("YES")
    g = gray(al, bl)
    p = [l2p(gi) for gi in g]
    print(' '.join(map(str, p)))
else:
    print("NO")

### FIXED CODE ###

n, a, b = [int(i) for i in input().split(" ")]

def p2l(x):
    l = []
    for i in range(0, n):
        l = [x % 2] + l
        x = x // 2
    return l

def l2p(x):
    return sum([x[i] * 2**(len(x) - i - 1) for i in range(0, len(x))])

al = p2l(a)
bl = p2l(b)

def gray(a, b):
    if len(a) == 1:
        return [a, b]
    
    for i in range(0, len(a)):
        if a[i] != b[i]:
            break
    ah = a[i]
    bh = b[i]
    del a[i]
    del b[i]
    
    c = [1 - a[0]] + a[1:]
    g1 = gray(a[:], c[:])
    g2 = gray(c[:], b[:])
    g1 = [h[0:i] + [ah] + h[i:] for h in g1]
    g2 = [h[0:i] + [bh] + h[i:] for h in g2]
    return g1 + g2

if sum(al) % 2 != sum(bl) % 2:
    print("YES")
    g = gray(al, bl)
    p = [l2p(gi) for gi in g]
    print(' '.join(map(str, p)))
else:
    print("NO")
### BUGGY CODE ###

import math
k=int(input())
total=0
info=[0]
for i in range(1,201):
    for j in range(1,201):
        if j<i:
            info.append(0)
            continue
        info.append(math.gcd(i,j))
        #print(str(i)+" "+str(j)+" "+str(math.gcd(i,j)))
#print(info[202])
#print(info)
for i in range(1,k+1):
    a=[]
    a.append(i)
    for j in range(1,k+1):
        a.append(j)
        for m in range(1,k+1):
            a.append(m)
            a=sorted(a)
            gcd=info[(a[0]-1)*200+a[1]]
            b=min(gcd,a[2])
            c=max(gcd,a[2])
            gcd=info[(b-1)*200+c]
            total+=gcd
            #print(gcd)
            #print(a)
            a=[i,j]
        a=[i]
print(total)

### FIXED CODE ###

import math
k=int(input())
total=0
info=[0]
for i in range(1,201):
    for j in range(1,201):
        if j<i:
            info.append(0)
            continue
        info.append(math.gcd(i,j))
        #print(str(i)+" "+str(j)+" "+str(math.gcd(i,j)))
#print(info[202])
#print(info)
for i in range(1,k+1):
    a=[]
    a.append(i)
    for j in range(1,k+1):
        a.append(j)
        for m in range(1,k+1):
            a.append(m)
            a=sorted(a)
            gcd=info[(a[0]-1)*200+a[1]]
            b=min(gcd,a[2])
            c=max(gcd,a[2])
            gcd=info[(b-1)*200+c]
            total+=gcd
            #print(gcd)
            #print(a)
            a=[i,j]
        a=[i]
print(total)
### BUGGY CODE ###

S = list(input())
Q = int(input())
spin = False
S_mae = []
for i in range(Q):
    temp = list(input().split())
    if temp[0] == "1":
        spin = not spin
    else:
        if spin:
            if temp[1] == "1":
                S.append(temp[2])
            else:
                S_mae.append(temp[2])
        else:
            if temp[1] == "1":
                S_mae.append(temp[2])
            else:
                S.append(temp[2])

res = ""
if spin:
    for i in range(len(S)):
        res += S.pop()
    res += "".join(S_mae)
else:
    for i in range(len(S_mae)):
        res += S_mae.pop()
    res += "".join(S)
print(res)


### FIXED CODE ###

import collections
S = collections.deque(list(input()))
Q = int(input())
spin = False
for i in range(Q):
    temp = list(input().split())
    if temp[0] == "1":
        spin = not spin
    else:
        if spin:
            if temp[1] == "1":
                S.append(temp[2])
            else:
                S.appendleft(temp[2])
        else:
            if temp[1] == "1":
                S.appendleft(temp[2])
            else:
                S.append(temp[2])

res = ""
if spin:
    S.reverse()
    print("".join(S))
else:
    print("".join(S))
### BUGGY CODE ###

n,w = map(int,input().split())
l =[list(map(int,input().split())) for i in range(n)]

dp = [[[0]*(3*n+1) for i in range(n+1)] for j in range(n+1)]
s = l[0][0]

for i in range(n):
    dt = l[i][0]-s
    for j in range(n):
        for k in range(3*n+1):
            if k -dt >= 0:
                dp[i+1][j+1][k] = max(dp[i][j+1][k],dp[i][j][k-dt]+l[i][1])
            else:
                dp[i+1][j+1][k] = dp[i][j+1][k]

ans = 0
for i in range(1,n+1):
    for j in range(3*n+1):
        if i*s+j <= w:
            ans = max(ans,dp[-1][i][j])
print(ans)

### FIXED CODE ###

n,w = map(int,input().split())
l =[list(map(int,input().split())) for i in range(n)]

dp = [[[0]*(3*n+1) for i in range(n+1)] for j in range(n+1)]
s = l[0][0]

for i in range(n):
    dt = l[i][0]-s
    for j in range(n):
        for k in range(3*n+1):
            if k -dt >= 0:
                dp[i+1][j+1][k] = max(dp[i][j+1][k],dp[i][j][k-dt]+l[i][1])
            else:
                dp[i+1][j+1][k] = dp[i][j+1][k]

ans = 0
for i in range(1,n+1):
    for j in range(3*n+1):
        if i*s+j <= w:
            ans = max(ans,dp[-1][i][j])
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
def lcm(x, y):
  return (x * y) // gcd(x, y)
def ll(numbers):
  return reduce(lcm, numbers, 1)
n=int(input())
a=list(map(int,input().split()))
l=ll(a)
x=0
m=10**9+7
for i in range(n):
  x+=(l//a[i])%m
  x=x%m
print(x)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
def lcm(x, y):
  return (x * y) // gcd(x, y)
def ll(numbers):
  return reduce(lcm, numbers, 1)
def modinv(a):
    return pow(a,m-2,m)
n=int(input())
a=list(map(int,input().split()))
l=ll(a)
x=0
m=10**9+7
lm=l%m
for i in range(n):
  x+=(lm*modinv(a[i]))%m
  x=x%m
print(x)