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

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

### FIXED CODE ###

from math import gcd
ans = 0
k = int(input())
 
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += gcd(k,gcd(i,j))

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

N=int(input())
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
  S=input()
  d[S]+=1
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
A=sorted(max_k_list)
for a in A:
  print(a)

### FIXED CODE ###

N=int(input())
S = [input() for i in range(N)]
S.sort()
import itertools
gr = itertools.groupby(S)
ans=[]
n=0
for key, group in gr:
  a=len(list(group))
  if a>n:
    ans=[]
    n=a
    ans.append(key)
  elif a==n:
    ans.append(key)
for a in ans:
  print(a)
### BUGGY CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

def sol():
    K = int(input())
    S = input()
    N = len(S)

    comb = Combination(N + K + 100)

    ans = 0
    L = 1
    R = pow(26, K, MOD)
    for l in range(K + 1):
        ans += L * comb.nhr(N, l) * R
        ans %= MOD

        L = L * 25 % MOD
        R = R * comb.inv[26] % MOD

    print(ans)
sol()

### FIXED CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

K = int(input())
S = input()
N = len(S)

comb = Combination(N + K + 100)

ans = 0
for l in range(K + 1):
    r = K - l
    ans += pow(25, l, MOD) * comb.nhr(N, l) * pow(26, r, MOD)
    ans %= MOD

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

from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

t_cnt=[0 for i in range(n)]
for i in range(q):
 p,x=map(int,input().split())
 t_cnt[p-1]+=x

cnt=[-1]*n
cnt[0]=t_cnt[0]

#seen=([0])
seen=[0]

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
   if i in seen:
    continue
   else:
    seen.append(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

### FIXED CODE ###

from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

t_cnt=[0 for i in range(n)]
for i in range(q):
 p,x=map(int,input().split())
 t_cnt[p-1]+=x

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
   if i in seen:
    continue
   else:
    seen.add(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)
### BUGGY CODE ###

s = input()
t = input()

dp = [ ['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+ s[i-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
#print(dp)
print(dp[len(s)][len(t)])


### FIXED CODE ###

s = input()
t = input()

dp = [ [0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+ 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#print(dp)

str = ''
while(i > 0 and j > 0):
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        str = s[i-1] + str
        i -= 1
        j -= 1

print(str)
### BUGGY CODE ###

import copy
N, M = map(int, input().split())
inputlist = []
prev = []
next = []
ans = [10000000] * (N + 1)
idxStock = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        prev.append(b)
        ans[b] = 1
    elif b == 1:
        prev.append(a)
        ans[a] = 1
    else:
        inputlist.append(a)
        inputlist.append(b)
while len(inputlist) != 0:
    for i in range(int(len(inputlist) / 2)):
        if prev.count(inputlist[i * 2]) != 0:
            idxStock.append(i)
            next.append(inputlist[i * 2 + 1])
            if ans[inputlist[i * 2 + 1]] ==10000000:
                ans[inputlist[i * 2 + 1]] = inputlist[i*2]
        elif prev.count(inputlist[i * 2 + 1]) != 0:
            idxStock.append(i)
            next.append(inputlist[i * 2])
            if ans[inputlist[i * 2]] == 10000000:
                ans[inputlist[i * 2]] = inputlist[i * 2 + 1]
    if len(next) == 0:
        print("No")
        exit()
    list.sort(idxStock, reverse=True)
    for i in idxStock:
        del inputlist[i*2]
        del inputlist[i * 2]
    idxStock.clear()
    prev.clear()
    prev = copy.copy(next)
    next.clear()
print("Yes")
for i in range(2, N + 1):
    print(ans[i])


### FIXED CODE ###

import copy
import queue
q = queue.Queue()
N, M = map(int, input().split())
nodes = [[] for i in range(N)]
idxStock = []
for i in range(M):
    a, b = map(int, input().split())
    nodes[a - 1].append(b - 1)
    nodes[b - 1].append(a - 1)

dist = [-1] * N
ans = [-1] * N

q.put(0)
while not q.empty():
    now = q.get()
    for i in nodes[now]:
        if dist[i] != -1:
            continue
        dist[i] = dist[now] + 1
        q.put(i)
        ans[i] = now
print("Yes")
for i in range(1, N):
    print(ans[i]+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
for _ in range(n):
    w, v = map(int, input().split())
    for wk in range(cap,w-1,-1):
        nv=val[wk-w]+v
        if val[wk]<nv:
            val[wk]=nv
print(val[-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))
### BUGGY CODE ###

N,X=map(int,input().split())
L=sorted(map(int,input().split()),reverse=True)
mod=10**9+7

from collections import defaultdict
D=defaultdict(int)
D[1,L[0]]=1

for l in L[1:]:
    ND=defaultdict(int)

    for c,s in D:
        k=D[c,s]

        if s+l+c-1<=X:
            ND[c+1,s+l]=(ND[c+1,s+l]+k*(c+1))%mod
        ND[c,s]=(ND[c,s]+k*(s-c*(l-1)))%mod

        for i in range(1,min(X-s-c+2,l+1)):
            ND[c,s+i]=(ND[c,s+i]+k*2*c)%mod

        for i in range(1,min(X-s-c+3,l+1)):
            ND[c-1,s+i]=(ND[c-1,s+i]+k*(c-1)*(l-i+1))%mod
    D=ND

print(D[1,X])

### FIXED CODE ###

N,X=map(int,input().split())
L=sorted(map(int,input().split()),reverse=True)
mod=10**9+7

D=[[0]*(X+1) for i in range(N//2+2)]
D[1][L[0]]=1

for l in L[1:]:
    ND=[[0]*(X+1) for i in range(N//2+1)]

    for c in range(1,N//2+1):
        for s in range(X+1):
            if D[c][s]==0:
                continue
            
            k=D[c][s]

            if s+l+c<=X and c+1<=N//2:
                ND[c+1][s+l]=(ND[c+1][s+l]+k*(c+1))%mod
            ND[c][s]=(ND[c][s]+k*(s-c*(l-1)))%mod

            for i in range(1,min(X-s-c+2,l+1)):
                ND[c][s+i]=(ND[c][s+i]+k*2*c)%mod

            if c==1:
                continue

            for i in range(1,min(X-s-c+3,l+1)):
                ND[c-1][s+i]=(ND[c-1][s+i]+k*(c-1)*(l-i+1))%mod
    D=ND

print(D[1][X])
### BUGGY CODE ###

N = int(input())
ss = []
ht = []
ans = 0

for i in range(N):
    s = sorted(input())
    if not s in ss:
        ss.append(s)
        ht.append(1)
    else:
        ans += ht[ss.index(s)]
        ht[ss.index(s)] += 1

print(ans)


### FIXED CODE ###

N = int(input())
ss = {}
ht = []
ans = 0

for i in range(N):
    s = ''.join(sorted(input()))
    if not s in ss.keys():
        ss[s] = 1
    else:
        ans += ss[s]
        ss[s] += 1

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

#ABC125C-GCDonBlackboard.py

from sys import stdin
from fractions import gcd
from functools import reduce

input = stdin.readline

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

gcd_max = gcd_list(A)

for i in range(N):
    A_test = A[:i] + A[i+1:]
    gcd_test = gcd_list(A_test)
    if gcd_max <= gcd_test:
        gcd_max = gcd_test

print(gcd_max)


### FIXED CODE ###

#ABC125C-GCDonBlackboard.py

from sys import stdin
from sys import setrecursionlimit
#import random
from fractions import gcd
from functools import lru_cache

setrecursionlimit(1000000)

input = stdin.readline

N = int(input())
A = list(map(int, input().split()))
#A = [random.randrange(1,10**9) for _ in range(N)]

@lru_cache(maxsize=None)
def L(i):
    if i == 0:
        return 0
    else:
        return gcd(L(i-1),A[i-1])

@lru_cache(maxsize=None)
def R(i):
    if i == N:
        return 0
    else:
        return gcd(R(i+1),A[i])

M = []

for i in range(N):
    M.append(gcd(L(i), R(i+1)))

print(max(M))
### BUGGY CODE ###

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

N = int (input())
L = list(map(int, input().split()))
L.sort()
count = 0

while len(L) > 2:
    for i in range(2,len(L)):
        if L[i] < L[0] + L[1]:
                count += 1
        if len(L) > 3:
            for j in range(3,len(L)):
                if L[j] < L[0] + L[i] and i < j:
                    count += 1
    del(L[0])

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left

N = int (input())
L = list(map(int, input().split()))
L.sort()

count = 0

for i in range(len(L)-2):
    for j in range(i+1,len(L)-1):
        count += bisect_left(L,L[i]+L[j]) - j - 1
        
print(count)
### BUGGY CODE ###

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

def make_array(dims,fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    ret = []
    nxt = dims[1:]
    for i in range(dims[0]):
        ret.append(make_array(nxt,fill))
    return ret
S = sum(X)+1
dp = make_array([N+2,N+2,S],0)
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for s in range(S-X[i]):
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
            dp[i+1][j][s] += dp[i][j][s]
ans = 0
for j in range(1,N+1):
    for s in range(1,S+1):
        if j*A == s:
            ans += dp[-2][j][s]
print(ans)

### FIXED CODE ###

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

def make_array(dims,fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    ret = []
    nxt = dims[1:]
    for i in range(dims[0]):
        ret.append(make_array(nxt,fill))
    return ret
S = sum(X)+1
dp = make_array([N+2,N+2,S],0)
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for s in range(S-X[i]):
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
            dp[i+1][j][s] += dp[i][j][s]
ans = 0
for j in range(1,N+1):
    for s in range(1,S+1):
        if j*A == s:
            ans += dp[-2][j][s]
print(ans)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left+1, mid-1
    else:
        left, right = mid+1, right-1


### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
X.sort()
Y.sort()
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
X.sort()
Y.sort()
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)
### BUGGY CODE ###

from heapq import nlargest
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    bit = 1<<i
    for j in range(1<<N):
        if j & bit:
            f[j] = nlargest(2, f[j]+f[j^bit])
Ans = [sum(f[1])]
for v in f[2:]:
    Ans.append(max(Ans[-1], sum(v)))
print("\n".join(map(str, Ans)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

reverseFlag = False

S = input()
Q = int(input())

for i in range(Q):
    TFC = input().split(' ')
    if TFC[0] == '1':
        if reverseFlag:
            reverseFlag = False
        else:
            reverseFlag = True
    else:
        if TFC[1] == '1':
            if reverseFlag:
                S = S + TFC[2]
            else:
                S = TFC[2] + S
        else:
            if reverseFlag:
                S = TFC[2] + S
            else:
                S = S + TFC[2]
if reverseFlag:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

reverseFlag = False

S = input()
Q = int(input())
S_mae = ''
S_ato = ''

for i in range(Q):
    TFC = input().split(' ')
    if TFC[0] == '1':
        reverseFlag = not reverseFlag
    else:
        if TFC[1] == '1':
            if reverseFlag:
                S_ato = S_ato + TFC[2]
            else:
                S_mae = TFC[2] + S_mae
        else:
            if reverseFlag:
                S_mae = TFC[2] + S_mae
            else:
                S_ato = S_ato + TFC[2]
if reverseFlag:
    print(S_ato[::-1] + S[::-1] + S_mae[::-1])
else:
    print(S_mae + S + S_ato)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
P = 998244353
table = [[0 for _ in range(S+1)] for _ in range(N)]
table[0][0] = 2
if A[0]<=S:
    table[0][A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    for j in range(S+1):
        table[i][j] += (2*table[i-1][j])
        if j+Ai<=S:
            table[i][j+Ai] += table[i-1][j] 

print(table[N-1][S]%P)


### FIXED CODE ###

import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
    table[0, A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    table[i] += 2*table[i-1]
    if Ai <= S:
        table[i][Ai:] += table[i-1][:S-Ai+1]
    table[i] = table[i]%P

print(table[N-1][S])
### BUGGY CODE ###

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
n=int(input())
s=time.time()
factors=defaultdict(lambda:[])
for i in range(2,3300):
    if(i not in factors):
        for j in range(i,10000001,i):
            factors[j].append(i)
ans=1
# print(factors)
# print(time.time()-s)
for i in range(2,n+1):
    tt=1
    tn=i
    for j in factors[i]:
        temp=0
        while(tn%j==0):
            temp+=1
            tn=tn//j
        tt*=(temp+1)
    if(tn!=1):
        tt*=2
    ans+=i*tt
print(ans)
# print(time.time()-s)





### FIXED CODE ###

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
def find(a):
    return (a*(a+1))//2
n=int(input())
ans=0
for i in range(1,n+1):
    ans+=i*find(n//i)
print(ans)
### BUGGY CODE ###

import heapq

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for i in range(n+1)]
adjt = [[] for i in range(n+1)]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

ans = [0]*(n+1)
ans[n] = yen -dist_s[n] - dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i] - dist_t[i])
print(*ans[1:], sep = '\n')


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]

k = 1
for i in range(N):
	k = (k * A[i])//kouyaku(k, A[i])
ans = 0
for i in range(N):
	ans += k//A[i]
print(ans%MOD)

### FIXED CODE ###

def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def prime(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > x**(1/2): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = prime(10**6)
pd = {}
for i in range(len(primes)):
	pd[primes[i]] = i
MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]
K = [0]*len(primes)
for i in range(N):
	a = A[i]
	for i in range(len(primes)):
		p = primes[i]
		if a == 1:
			break
		elif p > 1000:
			K[pd[a]] = 1
			break
		else:
			cou = 0
			while a%p==0:
				a = a//p
				cou += 1
			K[i] = max(cou, K[i])
kv = 1
for i in range(len(primes)):
	kv *= power(primes[i], K[i])
	kv %= MOD
ans = 0
for i in range(N):
	ans += divide(kv, A[i])
	ans %= MOD
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [[0] * T for _ in range(N + 1)]

    for i in range(N):
        for t in range(T):
            if t - D[i][0] >= 0:
                dp[i + 1][t] = dp[i][t - D[i][0]] + D[i][1]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        if ans < dp[i][T - 1] + D[i][1]:
            ans = dp[i][T - 1] + D[i][1]

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

    dp1 = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp1[i + 1][t] = dp1[i][t - A[i]] + B[i]
            if dp1[i + 1][t] < dp1[i][t]:
                dp1[i + 1][t] = dp1[i][t]

    dp2 = [[0] * T for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for t in range(T):
            if 0 <= t - A[i]:
                dp2[i][t] = dp2[i + 1][t - A[i]] + B[i]
            if dp2[i][t] < dp2[i + 1][t]:
                dp2[i][t] = dp2[i + 1][t]

    ans = 0
    for i in range(N):
        tmp = max(dp1[i][t] + dp2[i + 1][T - t - 1] for t in range(T)) + B[i]
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()