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

# coding: utf-8
# Your code here!
N,T=map(int,input().split())

l=[]
for _ in range(N):
    a,b=map(int,input().split())
    l.append([a,b])

l.sort()

dp=[-1]*(6001)
dp[0]=0

for cand in l:
    for i in range(T)[::-1]:
        if dp[i]!=-1:
            dp[i+cand[0]]=max(dp[i+cand[0]],dp[i]+cand[1])
print(max(dp))



### FIXED CODE ###

# coding: utf-8
# Your code here!
N,T=map(int,input().split())

l=[]
for _ in range(N):
    a,b=map(int,input().split())
    l.append([a,b])

l.sort()

dp=[-1]*(6001)
dp[0]=0

for cand in l:
    for i in range(T)[::-1]:
        if dp[i]!=-1:
            dp[i+cand[0]]=max(dp[i+cand[0]],dp[i]+cand[1])
print(max(dp))
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
arr=[0,0,0]
for i in al:
    arr[i-1]+=1
dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
vis=[[[False for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
#a,b,c=arr
for c in range(n+1):
    for b in range(n+1):
        for a in range(n+1):
            if a==b==c==0:
                continue
            if 0<=c-1<=n and 0<=b+1<=n:
                dp[a][b][c]+=dp[a][b+1][c-1]*c/n
            if 0<=b-1<=n and 0<=a+1<=n:
                dp[a][b][c]+=dp[a+1][b-1][c]*b/n
            if 0<=a-1<=n:
                dp[a][b][c]+=dp[a-1][b][c]*a/n
            dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)

print(dp[arr[0]][arr[1]][arr[2]])

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
l = []
for i in range(1, n // 2 + 1):
  if n % i == 0:
    a = i
    b = n // i
    l.append(a + b - 2)
print(min(l))

### FIXED CODE ###

import math
n = int(input())
l = []
for i in range(1, int(math.sqrt(n)) + 1):
  if n % i == 0:
    a = i
    b = n // i
    l.append(a + b - 2)
print(min(l))
### BUGGY CODE ###

def comb(n):
    if n <= 1:
        return 0
    return n * (n - 1) // 2


def check(L):
    s = 0

    a = 0
    c = 0
    #print(L)
    for i in range(len(L)):
        if a != L[i]:
            s += comb(c)
            a = L[i]
            c = 1 
        else:
            c += 1
    s += comb(c)

    return s

N = int(input())
A = [int(n) for n in input().split(" ")]

D = {}
for i in range(len(A)):
    D[i] = A[i]

D = sorted(D.items(), key=lambda x: x[1])
V = {}
for i in range(len(D)):
    V[D[i][0]] = i

AA = sorted(A)

for k in range(N):
    AAA = list(AA)
    del(AAA[V[k]])
    print(check(AAA))



### FIXED CODE ###

def comb(n):
    if n <= 1:
        return 0
    return n * (n - 1) // 2


def check(L):
    r = {}
    a = 0
    c = 0
    for i in range(len(L)):
        if a != L[i]:
            if i != 0:
                r[a] = [comb(c), comb(c - 1)]
            a = L[i]
            c = 1 
        else:
            c += 1
    r[a] = [comb(c), comb(c - 1)]
    #print(r)
    return r

N = int(input())
A = [int(n) for n in input().split(" ")]

D = {}
for i in range(len(A)):
    D[i] = A[i]

D = sorted(D.items(), key=lambda x: x[1])
V = {}
for i in range(len(D)):
    V[D[i][0]] = i

AA = sorted(A)
rr = check(AA)
ss = 0
for k, v in rr.items():
    ss += v[0]
#print(ss)

for k in range(N):
    index = A[k]
    a = rr[index][0] - rr[index][1]
    print(ss - a)
### BUGGY CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
ifReached[s-1] = True
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in n_stack:
        print(count)
        break
    stack = tmp_stack

### FIXED CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = list(set(next))
    return start

stack = [s]
ifReached[s-1] = True
count = 0
while True:
    n_stack = list(set(indicate3(stack,path)))

    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in tmp_stack:
        print(count)
        break
    stack = tmp_stack
### BUGGY CODE ###

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

for i in range(q):
    b, c = map(int, input().split())
    list_a = [c if i == b else i for i in list_a]
    print(sum(list_a))


### FIXED CODE ###

import numpy as np

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

counts = np.zeros(100000, dtype=int)

ans = 0

for i in range(len(list_a)):
    counts[list_a[i]-1] += 1
    ans += list_a[i]

q = int(input())

for i in range(q):
    b, c = map(int, input().split())

    ans += counts[b-1] * (c - b)

    counts[c-1] += counts[b-1]
    counts[b-1] = 0

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

import sys

def main():
    n = int(input())
    A = list(map(int, input().split()))

    ans = 1
    for i in range(n):
        ans *= A[i]

    if ans > 10 ** 18:
        print('-1')
    else:
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))

    ans = 1

    if 0 in A:
        print(0)
        sys.exit()

    for i in range(n):
        ans *= A[i]
        if ans > 10 ** 18:
            print('-1')
            sys.exit()

    print(ans)


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

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

all_lst = []
odd_lst = []
flg = False
count = 0
for i in range(0, h-1, 2):
    for j in range(w):
        all_lst.append((i+1, j+1))
        if flg == True:
            count += 1
        if lst[i][j] % 2 == 1:
            odd_lst.append((i+1,j+1))
            if flg == True:
                flg = False
            else:
                flg = True
    for j in reversed(range(w)):
        all_lst.append((i+2, j+1))
        if flg == True:
            count += 1
        if lst[i+1][j] % 2 == 1:
            odd_lst.append((i+2, j+1))
            if flg == True:
                flg = False
            else:
                flg = True
if h % 2 == 1:
    for j in range(w):
        all_lst.append((h, j+1))
        if flg == True:
            count += 1
        if lst[-1][j] % 2 == 1:
            odd_lst.append((h, j+1))
            if flg == True:
                flg = False
            else:
                flg = True 

print(count)
flg = False
for i, tpl in enumerate(all_lst):
    if flg == True:
        print(all_lst[i-1][0], all_lst[i-1][1], all_lst[i][0], all_lst[i][1])
    if tpl in odd_lst:
        if flg == False:
            flg = True
        else:
            flg = False

### FIXED CODE ###

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

count = 0
ans = []
for i in range(0, h-1, 2):
    for j in range(w):
        if lst[i][j] % 2 == 1:
            count += 1
            if j == w-1:
                lst[i+1][j] += 1
                ans.append((i+1, j+1, i+2, j+1))
            else:
                lst[i][j+1] += 1
                ans.append((i+1, j+1, i+1, j+2))
    for j in reversed(range(w)):
        if lst[i+1][j] % 2 == 1:
            if j == 0 and i+1 == h-1:
                pass
            elif j == 0:
                lst[i+2][j] += 1
                ans.append((i+2, j+1, i+3, j+1))
                count += 1
            else:
                lst[i+1][j-1] += 1
                ans.append((i+2, j+1, i+2, j))
                count += 1
if h % 2 == 1:
    for j in range(w):
        if lst[-1][j] % 2 == 1:
            if j == w-1:
                pass
            else:
                lst[-1][j+1] += 1
                ans.append((h, j+1, h, j+2))
                count += 1
                
print(count)
for a,b,c,d in ans:
    print(a,b,c,d)
### BUGGY CODE ###

S = list(input())
Q = int(input())
inversion_flg = False
# L = [input().split() for _ in range(Q)]

for i in range(Q):
    L = input().split()
    if L[0] == '1':
        if inversion_flg:
            inversion_flg = False
        else:
            inversion_flg = True
    if L[0] == '2':
        if not inversion_flg:
            if L[1] == '1':
                S = [L[2]] + S
            else:
                S = S + [L[2]]
        else:
            if L[1] == '2':
                S = [L[2]] + S
            else:
                S = S + [L[2]]



# print(L)
if not inversion_flg: 
    print(''.join(S))
else:
    # S.reverse()
    S = S[::-1]
    print(''.join(S))

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))

diff = [a[i] + a[i+1] for i in range(N-1)]

counter = 0

for i in range(N-2):
    while diff[i] > x:
        counter += 1
        diff[i] -= 1
        diff[i+1] -= 1
if diff[N-2] > x:
    counter += diff[N-2] - x

print(counter)

### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))

a += [0]
counter = 0

for i in range(N-1):
    flow = a[i] + a[i+1] - x
    if flow > 0:
        counter += flow
        a[i+1] = max(a[i+1]-flow, 0)

print(counter)
### BUGGY CODE ###

import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    X = nl()
    for i in range(n):
        print(sorted((X[:i] + X[i + 1:]))[(n - 1) // 2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    X = nl()
    X_s = sorted(X)
    mid = X_s[n // 2]
    del_mid = (X_s[:n // 2] + X_s[n // 2 + 1:])[(n - 1) // 2]
    for x in X:
        if x < mid:
            print(mid)
        elif x > mid:
            print(X_s[n // 2 - 1])
        else:
            print(del_mid)


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

n=int(input())
from collections import Counter as co
l=co(map(int,input().split()))
ans=set()
for k in l:
    if l[k]>=2:ans.add(k)
    for j in range(2*k,10**6+1,k):
        if j in l:
            ans.add(j)
        
        
print(len(l)-len(ans))

### FIXED CODE ###

n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,10**6+1,k):

        if i in l:
            ng.add(i)
            
            

print(ans-len(ng))
### BUGGY CODE ###

n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)


### FIXED CODE ###

n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)
### BUGGY CODE ###

import heapq as hq
from math import ceil
N, H = map(int, input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
ab.sort(key=lambda x:x[1], reverse=True)
ab.sort(key=lambda x:x[0], reverse=True)
ma, mb = ab[0]
ab = ab[1:]
q = []
for _,b in ab:
    if b > ma:
        hq.heappush(q, b)
ans = float("inf")

for l in range(len(q)+1):
    h = H
    cnt = l
    h -= sum(q[:l])
    if h <= 0:
        ans = min(ans, cnt)
        continue
    h -= mb
    cnt += 1
    if h <= 0:
        ans = min(ans, cnt)
        continue
    cnt += ceil(h/ma)
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import heapq as hq
from itertools import accumulate
from math import ceil
N, H = map(int, input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
ab.sort(key=lambda x:x[1], reverse=True)
ab.sort(key=lambda x:x[0], reverse=True)
ma, mb = ab[0]
q = [ab[i][1] for i in range(1, N)]
q.sort(reverse=True)
ans = float("inf")
acc = [0]+list(accumulate(q, lambda x,y:x+y))
for l in range(len(q)+1):
    h = H
    cnt = l
    h -= acc[l]
    if h <= 0:
        ans = min(ans, cnt)
        continue
    h -= mb
    cnt += 1
    if h <= 0:
        ans = min(ans, cnt)
        continue
    cnt += ceil(h/ma)
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

import sys

n,p = list(map(int,input().split())); s = input()

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    sys.exit()
    
res = [0] * p
arr = [int(s[i:])%p for i in range(n)]
for i in arr:
    res[i] += 1
for i in res:
    ans += i*(i-1)
ans //= 2
ans += res[0]
    
print(ans)

### FIXED CODE ###

n,p = list(map(int,input().split())); s = [int(i) for i in input()]

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p == 0:
            ans += i+1
    print(ans)
    
else:
    s = s[::-1]
    res = [0] * p
    arr = [0] * n
    tmp = 0
    for i in range(n):
        tmp += s[i]*pow(10,i,p)
        tmp %= p
        arr[i] = tmp
    for i in arr:
        res[i] += 1
    for i in res:
        ans += i*(i-1)
    ans //= 2
    ans += res[0]
        
    print(ans)
### BUGGY CODE ###

N = int(input())
Ts = []
for i in range(N):
  S = input()
  T = sorted(S)
  Ts.append(T)
r = 0
for i in range(N):
  for j in range(i+1, N):
    if Ts[i] == Ts[j]:
      r += 1
print(r)


### FIXED CODE ###

N = int(input())
Ts = []
for i in range(N):
  S = input()
  T = "".join(sorted(S))
  Ts.append(T)
Ts.sort()
r = 0
c = 1
for i in range(N-1):
  if Ts[i] == Ts[i+1]:
    c += 1
  else:
    r += c*(c-1)//2
    c = 1
r += c*(c-1)//2
print(r)
### BUGGY CODE ###

from operator import itemgetter
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=itemgetter(1))

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  def sum(self,i):
    s=0
    while i>0:
      s+=self.tree[i]
      i-=i&-i
    return s

  def add(self,i,x):
    while i<=self.size:
      self.tree[i]+=x
      i+=i&-i

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

for i in range(q):
  print(ans[i])

### FIXED CODE ###

n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  def sum(self,i):
    s=0
    while i>0:
      s+=self.tree[i]
      i-=i&-i
    return s

  def add(self,i,x):
    while i<=self.size:
      self.tree[i]+=x
      i+=i&-i

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

for i in range(q):
  print(ans[i])
### BUGGY CODE ###

A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = x
for i in range(A):
    for j in range(A):
        dp[i] = min(dp[i],x[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))


### FIXED CODE ###

import numpy as np
N, x = map(int, input().split())
a = np.array(list(map(int, input().split())))
b = np.copy(a)
ans = float('inf') 
for i in range(N):
    c = np.roll(a,i)
    b = np.minimum(b,c)
    ans = min(ans, sum(b)+i*x)
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    N = len(S)
    K = int(input())
    top_k = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            st = S[i:j]
            top_k.append(st)
            if len(top_k) > K:
                top_k = list(set(top_k))
                top_k.sort()
                top_k = top_k[:K]
    top_k.sort()
    print(top_k[-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    N = len(S)
    K = int(input())
    top_k = []
    for i in range(N):
        for j in range(i + 1, min([i + K, N]) + 1):
            st = S[i:j]
            top_k.append(st)
            if len(top_k) > K:
                top_k = list(set(top_k))
                top_k.sort()
                top_k = top_k[:K]
    top_k.sort()
    print(top_k[-1])


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

X, Y, A, B, C = list(map(int, input().split()))
R = list(map(int, input().split()))
G = list(map(int, input().split()))
C = list(map(int, input().split()))

R.sort()
R.reverse()
G.sort()
G.reverse()
C.sort()
C.reverse()

R = R[:X]
G = G[:Y]

temp = 0
  
for i in range(len(C)) :
  if((X==0) and (Y==0)) :
    break
  if(X==0) :
    last = G[Y-1]
    Y -= 1
    
  else :
    if(Y==0) :
      last = R[X-1]
      X -= 1
    else :
      if(R[X-1] < G[Y-1]) :
        last = R[X-1]
        X -= 1
      else :
        last = G[Y-1]
        Y -= 1

  if(C[i] < last) :
    if(i == 0) :
      answer = sum(R[:X]) + sum(G[:Y]) + last
    else :
      break
  else :
    answer = sum(R[:X]) + sum(G[:Y]) + sum(C[:i+1])
    
print(answer)

### FIXED CODE ###

X, Y, A, B, C = list(map(int, input().split()))
R = list(map(int, input().split()))
G = list(map(int, input().split()))
C = list(map(int, input().split()))

R.sort()
R.reverse()
G.sort()
G.reverse()
C.sort()
C.reverse()

R = R[:X]
G = G[:Y]

temp = 0
  
for i in range(len(C)) :
  if((X==0) and (Y==0)) :
    i = i-1
    break
  if(X==0) :
    last = G[Y-1]
    Y -= 1
    
  else :
    if(Y==0) :
      last = R[X-1]
      X -= 1
    else :
      if(R[X-1] < G[Y-1]) :
        last = R[X-1]
        X -= 1
      else :
        last = G[Y-1]
        Y -= 1

  if(C[i] < last) :
      break
  else :
    last = C[i]
    
print(sum(R[:X])+sum(G[:Y])+sum(C[:i])+last)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L=sorted(L,reverse=True)
count=0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[k]+L[j]<=L[i]:
        break
      if L[i]+L[k]<=L[j]:
        break
      if L[j]+L[i]>L[k]:
        count+=1
      
print(count)

### FIXED CODE ###

import bisect
 
N=int(input())
L=list(map(int,input().split()))
 
L.sort()
count=0
for i in range(N):
  for j in range(i+1,N):
    c=L[i]+L[j]
    index=bisect.bisect_left(L,c)
    count+=max(0,index-j-1)
print(count)
### BUGGY CODE ###

import numpy as np
N, Q = map(int, raw_input().split())
S = raw_input()
L = np.zeros(Q)
R = np.zeros(Q)
for i in range(Q):
    L[i], R[i] = map(int, raw_input().split())
num = np.zeros(Q)
for i in range(Q):
    for j in range(int(L[i]), int(R[i])):                                                                           
        if S[j-1] == "A":
            if j <= N:
                if S[j] == "C":
                    num[i] += 1
for i in num:
    print int(i)


### FIXED CODE ###

import numpy as np
N, Q = map(int, raw_input().split())
S = raw_input()
L = np.zeros(Q)
R = np.zeros(Q)
for i in range(Q):
    L[i], R[i] = map(int, raw_input().split())
num = np.zeros(N)
num_tmp = 0
for i in range(1,N):
    if S[i-1:i+1] == "AC":
        num_tmp += 1
    num[i] = num_tmp
for i in range(Q):
    print int(num[int(R[i]-1)] - num[int(L[i]-1)])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# C - XYZ Triplets
def get_f(n):
	count = 0
	
	for x in range(1, n):
		if x ** 2 > n:
			return count
		else:
			for y in range(1, n):
				if x ** 2 + y ** 2 < n:
					for z in range(1, n):
						calc = x ** 2 + y ** 2 + x * y
						
						if calc < n:
							if z ** 2 + y * z + z * x == n - calc:
								count += 1
						else:
							break
		
	return count


N = int(input())

for n in range(1, N + 1):
	print(get_f(n))

### FIXED CODE ###

import sys
input = sys.stdin.readline

# C - XYZ Triplets
def calc(x, y, z):
	return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


N = int(input())
ans = [0] * (N + 1)

for x in range(1, 100):
	for y in range(1, 100):
		for z in range(1, 100):
			i = calc(x, y, z)
			
			if i > N:
				break
			else:
				ans[i] += 1

for i in range(1, N + 1):
	print(ans[i])
### BUGGY CODE ###

import numpy as np


def main():
	L, R = [int(x) for x in input().split()]
	tmp_min = np.inf
	for i in range(L, R+1):
		for j in range(i+1, R+1):
			if (i * j) % 2019 < tmp_min:
				tmp_min = (i * j) % 2019
	print(tmp_min)

if __name__ == "__main__":
	main()


### FIXED CODE ###

import numpy as np


def main():
	L, R = [int(x) for x in input().split()]
	tmp_min = np.inf
	for i in range(L, R+1):
		for j in range(i+1, R+1):
			if (i * j) % 2019 < tmp_min:
				tmp_min = (i * j) % 2019
				if tmp_min == 0:
					print(tmp_min)
					exit()
	print(tmp_min)

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

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

num = a[0]
for i in range(1, n):
	num = (num // fractions.gcd(num, a[i]))*a[i]
 
ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007
 
print(ans)

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))