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

N,W = map(int,input().split())
w,v = [0]*N , [0]*N
for i in range(N):
  w[i],v[i] = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for k in range(W+1):
  dp[0][k] = 0
for i in range(N):
  for j in range(W+1):
    if j -w[i] <0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[-1][W])

### FIXED CODE ###

N,W = map(int,input().split())
w,v = [0]*N , [0]*N
for i in range(N):
  w[i],v[i] = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for k in range(W+1):
  dp[0][k] = 0
for i in range(N):
  for j in range(W+1):
    if j -w[i] <0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[-1][W])
### BUGGY CODE ###

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

l = []
for i in range(k+1):
    for j in range(k+1):
        l.append([i,j])
#print(len(l))

q = 0
for r in range(k+1):
    for p in range(len(l)):
        if r + sum(l[p]) == s:
                q += 1

#print(k,s,l)
print(q)


### FIXED CODE ###

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

x = 0
l = []
for i in range(k+1):
    for j in range(k+1):
        if s-i-j >= 0 and s-i-j <= k:
            x += 1
print(x)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())
A = [[]]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#AR[i][j] => iにとって選手jとの試合が何番目か
AR = [[]]
for i in range(1,N+1):
    AR.append([0]*(N+1))
    for j in range(1,N):
        b = A[i][j]
        AR[i][b] = j

edges = {}
for i in range(1,N+1):
    for j in range(i+1,N+1):
        edges[(i,j)] = []
        jForI = AR[i][j]
        if jForI < N-1:
            nxForI = A[i][jForI+1]
            edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
        iForJ = AR[j][i]
        if iForJ < N-1:
            nxForJ = A[j][iForJ+1]
            edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))

steps = {}
def dfs(i,j):
    #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
    if (i,j) not in steps:
        steps[(i,j)] = 0
        res = 1
        for a,b in edges[(i,j)]:
            res = max(res,dfs(a,b)+1)
        steps[(i,j)] = res
    elif steps[(i,j)] == 0:
        print(-1)
        exit()
    return steps[(i,j)]

ans = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        ans = max(ans,dfs(i,j))
print(ans)


### FIXED CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a_c = a
for i in range(n):
    a_c[i] -= i
min_a_c = min(a_c)
max_a_c = max(a_c)
scores = []
for j in range(min_a_c, max_a_c + 1):
    tmp_score = 0
    for i in range(n):
        tmp_score += abs(a_c[i] - j)
    scores.append(tmp_score)
print(min(scores))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a_c = a
for i in range(n):
    a_c[i] -= i
a_c.sort()
med = a_c[n // 2]
score = 0
for i in range(n):
    score += abs(a_c[i] - med)
print(score)
### BUGGY CODE ###

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

res = 0
for num in range(n):
    if a.count(num+1) > 0:
        res += a.count(num+1)*(a.count(num+1)-1)//2

for a_k in a:
    cnt = a.count(a_k)
    print(res - (cnt-1)*(cnt - (cnt-2))//2)

### FIXED CODE ###

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

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0
B = B+B+B
print(B[k-1])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
### BUGGY CODE ###

def main():
    from array import array
    from numpy import int32,searchsorted
    s=searchsorted
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    d=int32(t[-q:])
    t=t[:-q]
    x=int32(t[2::3])
    for x,l,r in sorted(zip(x,s(d,t[::3]-x)+N0,s(d,t[1::3]-x)+N0))[::-1]:
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
import bisect

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	#print(pp)		
	for p in pp:
		if v % p == 0:
			return False, 0
		#if v < 2*p:
		#	return True, 0
	return True, 0
			

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	al = lin()
	al.sort()
	
	unique_al = list(set(al))
	unique_al.sort()
	
	al_counter = collections.Counter(al)
	ok=[v for v in al_counter.keys() if al_counter[v] == 1]
	d = {v:i for i,v in enumerate(ok)}
	max_v = 10**6+1
	for check in unique_al:
		for v in range(2*check, max_v, check):
			if v in d:
				ok[d[v]]=0
				
	return sum([v > 0 for v in ok ])
		
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n, m = [int(x) for x in input().split()]
A = [int(input()) for i in range(m)]
pattern = [1]
for i in range(1, n + 1):
    if i in A:
        pattern.append(0)
        continue
    if i == 1:
        pattern.append(pattern[i - 1])
    if i > 1:
        pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
print(pattern[n])


### FIXED CODE ###

MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()
### BUGGY CODE ###

n = int(input())
ans = 0

while n > ans:
    ans += ans
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

while n > ans:
    ans += 111
print(ans)
### BUGGY CODE ###

from math import factorial
from itertools import combinations

n = int(input())
A = tuple(map(int,input().split())) 

def comb(n,r):
    return factorial(n)//(factorial(n-r) * factorial(r))

res = []
for a,b in combinations(A,2):
    if a < b:
        a,b = b,a
    res.append([comb(a,b),a,b])

res.sort(reverse=True)
print(res[0][1],res[0][2])



### FIXED CODE ###

n = int(input())
A = sorted(list(map(int,input().split())),reverse=True)
k = 10**10
for i in range(1,n):
    k = min(k,abs(A[0]/2 -A[i]))
    if k == abs(A[0]/2 -A[i]):
        ans = [A[0],A[i]]
print(ans[0],ans[1])
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
s = 0
for i in range(0,N-K+1):
    t = K
    for j in range(0,K):
        t = t+p[i+j]
    t = t/2
    if s < t:
        s = t
print (s)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
s = 0
for i in range(0,K):
    s = s+p[i]
u = s
for i in range(0,N-K):
    t = s+p[i+K]-p[i]
    if u < t:
        u = t
    s = t
print ((u+K)/2)
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(float, input().split()))
i=0
while i<m:
  i+=1
  tukaubasho=A.index(max(A))
  A[tukaubasho]=A[tukaubasho]/2
output=0
for a in A:
	output=output+(a//1)
print(int(output))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    index = bisect.bisect_left(city_dict[prefecture_id], year_of_establishment)
    city_dict[prefecture_id].insert(index, year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


### FIXED CODE ###

number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)
### BUGGY CODE ###

# 参考URL
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

#     def union(self, x, y):
#         x = self.find(x)
#         y = self.find(y)

#         if x == y:
#             return

#         if self.parents[x] > self.parents[y]:
#             x, y = y, x

#         self.parents[x] += self.parents[y]
#         self.parents[y] = x
        
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

ans = []
for i in range(N):
    links = set(uf_road.members(i)) & set(uf_train.members(i))
    ans.append(len(links))
    
print(' '.join(map(str, ans)))

### FIXED CODE ###

# 参考URL
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = sorted(list(map(int,input().split())), reverse=True)

for i in r:
    p_min = p[0]
    q_min = q[0]

    if p_min > i and q_min > i:
        break

    p_min_diff = i - p_min
    q_min_diff = i - q_min

    if p_min_diff >= q_min_diff and p_min_diff > 0:
        del p[0]
        p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        del q[0]
        q.append(i)

print(sum(p) + sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
B = list(map(lambda x:len(bin(x&-x)), A))
if all(map(lambda x:x==B[0], B[1:])):
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))
else:
    print(0)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
b0 = AA[0]&-AA[0]
for a in AA[1:]:
    if b0 != a&-a:
        print(0)
        break
else:
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))
### BUGGY CODE ###

import fractions


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

a=A[0]
for b in A:
    a = a * b / fractions.gcd(a, b)

count=0
for i in A:
    count+=a/i

print(int(count)%((10**9)+7))

### FIXED CODE ###

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

a=A[0]
for b in A:
    a = (a * b) // fractions.gcd(a, b)

count=0
for i in A:
    count+=a//i

print((count%((10**9)+7)))
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())
if N > B:
	N = B
ans = 0
for x in range(1, N+1):
	y = math.floor(A * x / B) - A * math.floor(x / B)
	ans = max(ans, y)
print(ans)

### FIXED CODE ###

import math
A, B, N = map(int, input().split())
if N >= B:
	N = B - 1
ans = math.floor(A * N / B)
print(ans)
### BUGGY CODE ###

N, X = map(int, input().split())
city = list(map(int, input().split()))
a = []

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

for i in range(N):
	a.append(abs(city[i] - X))
	a = sorted(a, reverse = True)
	
s = a.pop(0)

while a:
	s = gcd(s, a.pop(0))
	if s == 1:
		break
print(s)

### FIXED CODE ###

from fractions import gcd

N, X = (int(i) for i in input().split())

x = [abs(int(i) - X) for i in input().split()]  
for i in range(1,N):
	x[i] = gcd(x[i-1], x[i])

print(x[-1])
### BUGGY CODE ###

import sys

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

c = None

for a in A:
    if A.count(a) >= 2:
        if c is not None:
            print(c * a)
            sys.exit()
        c = a
        A.remove(a)
        A.remove(a)
print(0)


### FIXED CODE ###

import sys

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

mstack = []
stack = [0]
for a in A:
    if a == stack[-1]:
        mstack.append(a)
        stack.pop()
        if len(mstack) >= 2:
            print(mstack[-1] * mstack[-2])
            sys.exit()
    else:
        stack.append(a)
print(0)
### BUGGY CODE ###

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

count = 0

for i in range(N - 2):
    a = lengths[i]
    for j in range(i + 1, N - 1):
        b = lengths[j]
        
        L, R = j, N
        while R - L > 1:
            C = (L + R) // 2
            c = lengths[C]
            if c < a + b:
                L = C
            else:
                R = C
        
        count += L - j

print(count)


### FIXED CODE ###

import bisect


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

ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        k = bisect.bisect_left(L, L[i] + L[j])
        ans += k - (j + 1)

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

from fractions import gcd
import math

a, b = [int(elem) for elem in input().split()]

cf = []
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
       cf.append(i)
       
# dest = int(math.sqrt(min(a, b)))
if len(cf) > 1:
    res = [cf[0], cf[1]]
    cf.pop(0)
    cf.pop(0)

    j = 0
    while True:
        if j >= len(cf):
            break
        flag = 0
        for elem in res[1:]:
            if cf == []:
                break
            if gcd(cf[j], elem) != 1:
                cf.pop(j)
                flag = 1
                break
        if flag == 0:
            res.append(cf[j])
            cf.pop(j)
else:
    res = [cf[0]]
print(len(res))

### FIXED CODE ###

a, b = [int(elem) for elem in input().split()]

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

a_lst = factorize(a)
b_lst = factorize(b)
res = list(set(a_lst) & set(b_lst))
print(len(res) + 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  3 22:47:34 2018
ALDS1_6_A
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n+1)]

def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    
    for j in range(n):
        c[a[j]] += 1
    
    for i in range(1, k+1):
        c[i] += c[i-1]
        
    for j in reversed(range(n)):
        #print(j, a[j], c[a[j]])
        b[c[a[j]]] = a[j]
        c[a[j]] -= 1
    
k = max(a)    
counting_sort(a, b, k)
print(b[1],end='')
for i in range(2,n+1):
    print(' {}'.format(b[i]), end='')
print()


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  3 22:47:34 2018
ALDS1_6_A
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n+1)]

def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    
    for aj in a:
        c[aj] += 1
    
    for i in range(1, k+1):
        c[i] += c[i-1]
        
    for j in reversed(range(n)):
        #print(j, a[j], c[a[j]])
        b[c[a[j]]] = a[j]
        c[a[j]] -= 1
    
k = max(a)    
counting_sort(a, b, k)
print(b[1],end='')
for i in range(2,n+1):
    print(' {}'.format(b[i]), end='')
print()