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

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

### FIXED CODE ###

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))
### BUGGY CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
for i in range(q):
  #print(d2)
  if d.get(b[i]):
    removed=d.pop(b[i])
    _=d2.pop(b[i])
    d[c[i]]+=removed
    d2[c[i]]=c[i]*d[c[i]]
  else:
    pass
  #print((np.array(list(d2.values()))))
  print(np.sum(np.array(list(d2.values()))))
  


### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["#"*(w+2)]
ans=[]
for i in range(h):
    grid.append("#"+input()+"#")
grid.append("#"*(w+2))
for i in range(h*w):
    for j in range(h*w):
        if grid[i//w+1][i%w+1]=="." and grid[j//w+1][j%w+1]==".":
            sx,sy,gx,gy=i//w+1,i%w+1,j//w+1,j%w+1
            que=deque([[sx,sy,0]])
            while True:
                q=que.popleft()
                if q[0]==gx and q[1]==gy:
                    ans.append(q[2])
                    break
                for x,y in v:
                    if grid[q[0]+x][q[1]+y]==".":
                        que.append([q[0]+x,q[1]+y,q[2]+1])
print(max(ans))

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["#"*(w+2)]
ans=[]
for i in range(h):
    grid.append("#"+input()+"#")
grid.append("#"*(w+2))
for i in range(h*w):
    ch=[[0]*(w+2) for i in range(h+2)]
    if grid[i//w+1][i%w+1]==".":
        sx,sy=i//w+1,i%w+1
        que=deque([[sx,sy,0]])
        while len(que):
            q=que.popleft()
            ch[q[0]][q[1]]=1
            ans.append(q[2])
            for x,y in v:
                if grid[q[0]+x][q[1]+y]=="." and ch[q[0]+x][q[1]+y]==0:
                    ch[q[0]+x][q[1]+y]=1
                    que.append([q[0]+x,q[1]+y,q[2]+1])
            
print(max(ans))
### BUGGY CODE ###

import numpy as np

N, K = [int(x) for x in input().split()]
A = np.array([int(x) for x in input().split()])

L = np.max(A)

ans = L
for l in range(1, L):
    counter = np.sum(A // l)
    if counter <= K:
        ans = l
        break

print(ans)

### FIXED CODE ###

import numpy as np

N, K = [int(x) for x in input().split()]
A = np.array([int(x) for x in input().split()])
I = np.array([1] * N)

L = np.max(A)

ans = L
low = 1
high = L
while 1:
    if low == high:
        ans = low
        break
    
    mid = (low + high) // 2
    if np.sum((A - I) // mid) <= K:
        high = mid
    else:
        low = mid + 1

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

def returnmax(numbers, i, N):
    nowmax = 0
    for j in range(N):
        if j != i:
            if nowmax < numbers[j]:
                nowmax = numbers[j]
    return nowmax
    
numbers = []
N = int(input())
for i in range(N):
    numbers.append(int(input()))
for i in range(N):
    print(returnmax(numbers, i, N))


### FIXED CODE ###

def returnsecond(numbers, N):
    first = 0
    firc = 0;
    second = 0
    for j in range(N):
        if first < numbers[j]:
            first = numbers[j]
            firc = j
    for j in range(N):
        if(j != firc and second <= numbers[j]):
            second = numbers[j]

    return first, second;


numbers = []
N = int(input())

for i in range(N):
    numbers.append(int(input()))
first, second = returnsecond(numbers, N)

for i in range(N):
    if numbers[i] != first:
        print(first)
    else:
        print(second)
### BUGGY CODE ###

n, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n-1)]
l.sort()
# print(l)

lq = [list(map(int, input().split())) for _ in range(q)]

ch = [[] for _ in range(n)]
ad = [[] for _ in range(n)]

for i in range(n-1):
    a, b = l[i][0]-1, l[i][1]-1
    ch[a].append(b)
    ad[b].append(a)
    for x in ad[a]:
        ch[x].append(b)
        ad[b].append(x)

# print(ch)
# print(ad)

ans = [0 for _ in range(n)]
for i in range(q):
    p, x = lq[i][0]-1, lq[i][1]
    ans[p] += x
    for j in ch[p]:
        ans[j] += x

ans = map(str, ans)
print(" ".join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
tree = [[] for _ in range(n)]

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

ans = [0 for _ in range(n)]

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

checked = [False] * n
checked[0] = True


def function(now, count):
    ans[now] += count
    for i in tree[now]:
        if checked[i] == False:
            checked[i] = True
            function(i, ans[now])

function(0, 0)

for a in ans:
    print(a)
### BUGGY CODE ###

MOD = 1000000007
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
d = {}
for i, ai in enumerate(a):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    p = q = 1
    for i in xrange(n - r + 1, n + 1):
        p = p * i % MOD
    for i in xrange(1, r + 1):
        q = q * i % MOD
    return (p * pow(q, MOD - 2, MOD)) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD


### FIXED CODE ###

MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

fac = {0: 1}
facinv = {}
for i in xrange(1, n + 2):
    fac[i] = fac[i - 1] * i % MOD
facinv[n + 1] = pow(fac[n + 1], MOD - 2, MOD)
for j in xrange(n, -1, -1):
    facinv[j] = facinv[j + 1] * (j + 1) % MOD


def ncr(n, r):
    return (fac[n] * facinv[n - r] * facinv[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
Kmax=-1
Ksum=0
for i in range(N-K+1):
    for j in range(K):
        Ksum+=P[i+j]
    if Ksum>Kmax:
        Kmax=Ksum
    Ksum=0
print((Kmax+K)/2)


### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
Q=[0]*(N+1)
Kmax=-1
for i in range(N):
    Q[i+1]+=P[i]+Q[i]

for j in range(N-K+1):
    if Q[j+K]-Q[j]>Kmax:
        Kmax=Q[j+K]-Q[j]
print((Kmax+K)/2)
### BUGGY CODE ###

H,W = map(int, input().split())
A=[]
B=[]
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
M=[[[] for _ in range(W)] for _ in range(H)]
m=0
for i in range(H):
    for j in range(W):
        M[i][j]=abs(A[i][j]-B[i][j])
        m=max(M[i][j],m)
r=m*(H+W)
dp=[[[False for _ in range(r+1)] for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])]=True
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        for k in range(r+1):
            if i==0:
                if k+M[i][j] <= r:
                    if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i][j-1][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif j==0:
                if k+M[i][j] <= r:
                    if dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i-1][j][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif k+M[i][j] <= r:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]] or dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                    dp[i][j][k]=True
            else:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i-1][j][abs(k-M[i][j])]:
                    dp[i][j][k]=True
for i in range(r+1):
    if dp[H-1][W-1][i]:
        print(i)
        break

### FIXED CODE ###

import numpy as np
import itertools

H,W=map(int,input().split())
A=[list(map(int, input().split())) for _ in range(H*2)]
M=[[abs(A[i][j]-A[H+i][j]) for j in range(W)] for i in range(H)]
m=max(max(j for j in i) for i in M)
r=m*(H+W)+1
dp=np.zeros((H,W,r),dtype='bool')
dp[0][0][M[0][0]]=True
it = itertools.product(range(H),range(W))
next(it)
for h,w in it:
    m=M[h][w]
    dp[h][w][m:] |= dp[h][w-1][:r-m] | dp[h-1][w][:r-m]
    dp[h][w][:r-m] |= dp[h][w-1][m:] | dp[h-1][w][m:]
    dp[h][w][:m] |= dp[h][w-1][m:0:-1] | dp[h-1][w][m:0:-1]

for i in range(r):
    if dp[-1][-1][i]:
        print(i)
        break
### BUGGY CODE ###

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

def getSum(s, e):
    sum = 0
    for i in range(s, e):
        sum = sum + list[i]
    return sum

prev = 0
for i in range(0,n-1):
    diff = abs(getSum(0, i+1) - getSum(i+1, n))
    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)



### FIXED CODE ###

n = int(input())
array = list(map(int,input().split(' ')))

left= array[0]
right = sum(array) - left

prev = 0
for i in range(0,n-1):
    diff = abs(left - right)
    left = left + array[i+1]
    right = right - array[i+1]

    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)
### BUGGY CODE ###

from bisect import bisect_left

def main():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr.sort()

    for i in range(m):
        b, c = map(int, input().split())
        idx = bisect_left(arr, c)

        if b >= idx:
            arr[:idx] = [c] * idx
        else:
            arr[:idx] = arr[b:idx] + [c] * b

    print(sum(arr))


main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    s = 0

    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda x: x[1], reverse=True)

    arr = []
    sum_b = 0
    for b, c in bc:
        arr += [c] * b
        sum_b += b
        if sum_b >= n:
            break

    arr += a
    arr.sort(reverse=True)
    print(sum(arr[:n]))


main()
### BUGGY CODE ###

n=(int)(input())
a = list(input() for i in range(n))
lis = sorted(list(set(a)))
big = []
maxi = 0
for i in lis:
  temp = a.count(i)
  if temp > maxi:
    big = [i]
    maxi = temp
  elif temp == maxi:
    big.append(i)
for i in range(len(big)):
  print(big[i])

### FIXED CODE ###

n=(int)(input())
a = sorted(list(input() for i in range(n)))
lis = sorted(list(set(a)))
big = [0 for i in range(len(lis))]
maxi = 0
counter = 1
check = 0
#print(a)
for i in range(len(a) - 1):
  #print(a[i])
  if a[i] == a[i + 1]:
    counter += 1
  else:
    big[check] = counter
    counter = 1
    check += 1
else:
  big[-1] = counter
maxi = max(big)
#print(lis, big)
for i in range(len(lis)):
  if big[i] == maxi:
    print(lis[i])
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
b_list = list(map(int, input().split()))
q = int(input())
a_list=[0]*100000
for i in b_list :
  a_list[i-1]+=1
count=sum(b_list)
for i in range(q):

  b, c = map(int, input().split())
  count+=(c-b)*a_list[b-1]
  print(count)

  a_list[c - 1] +=a_list[b-1]
  a_list[b - 1] = 0
### BUGGY CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])


### FIXED CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

tango = []
count = 0
for i in s:
  if i not in tango:
    count += 1
    tango.append(i)
print(count)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

print(len(list(set(s))))
### BUGGY CODE ###

import numpy
N, K = map(int, input().split())
A = numpy.array(list(map(int, input().split())))

dp = numpy.zeros(N, dtype=int)
for n in range(N):
    if n == 0:
        min_num = 0
    else:
        l = min(n, K)
        min_num = 10 ** 10
        for k in range(1, l + 1):
            min_num = min(abs(A[n] - A[n - k]) + dp[n - k], min_num)
    dp[n] = min_num

print(dp[-1])

### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

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

def abc(n:int,lst:list):
    l=list(map(lambda x:x[2],lst))
    if min(l)==0:
        M=max(map(lambda x:x[0],lst))+max(map(lambda x:x[1],lst))
        for x in range(101):
            for y in range(101):
                for h in range(M):
                    for i in range(n):
                        if max(0,h-abs(lst[i][0]-x)-abs(lst[i][1]-y)) ==lst[i][2]:
                            if i ==n-1:
                                return x,y,h
                        else:
                            break
    else:
        x0 =lst[0][0]
        y0=lst[0][1]
        h0 =lst[0][2]
        for x in range(101):
            for y in range(101):
                for i in range(1,n):
                    if abs(x0-x)+abs(y0-y)-abs(lst[i][0]-x)-abs(lst[i][1]-y) ==lst[i][2]-h0:
                        if i ==n-1:
                            return x,y,h0+abs(x0-x)+abs(y0-y)
                    else:
                        break
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
x,y,h =abc(n,lst)
print(x,y,h)


### FIXED CODE ###

def abc(n:int,lst:list):
    l0=list(filter(lambda x:x[2]==0,lst))
    l=list(filter(lambda x:x[2]!=0,lst))
    if len(l0):
        x0 =l[0][0]
        y0=l[0][1]
        h0 =l[0][2]
        ans=[]
        for x in range(101):
            for y in range(101):
                for i in range(len(l)):
                    if abs(x0-x)+abs(y0-y)-abs(l[i][0]-x)-abs(l[i][1]-y) == l[i][2]-h0:
                        if i ==len(l)-1:
                            ans.append([x,y,h0+abs(x0-x)+abs(y0-y)])
                    else:
                        break
        for xyh in ans:
            for i in range(len(l0)):
                if abs(l0[i][0]-xyh[0])+abs(l0[i][1]-xyh[1])>=xyh[2]:
                    if i == len(l0)-1:
                        return xyh
                else:
                    break
    else:
        x0 =lst[0][0]
        y0=lst[0][1]
        h0 =lst[0][2]
        for x in range(101):
            for y in range(101):
                for i in range(1,n):
                    if abs(x0-x)+abs(y0-y)-abs(lst[i][0]-x)-abs(lst[i][1]-y) ==lst[i][2]-h0:
                        if i ==n-1:
                            return x,y,h0+abs(x0-x)+abs(y0-y)
                    else:
                        break
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
x,y,h =abc(n,lst)
print(x,y,h)
### BUGGY CODE ###

#abc162 c
import math
k = int(input())
def gcds(x,y,z):
    n1 = math.gcd(x,y)
    n2= math.gcd(n1,z)
    return n2
total = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for t in range(1,k+1):
            total += gcds(i,j,t)
print(total)

### FIXED CODE ###

import math
k = int(input())

def gcds(x,y,z):
    n1 = math.gcd(x,y)
    n2= math.gcd(n1,z)
    return n2
total =0
for i in range(1,k+1):
    for j in range(1,k+1):
        if math.gcd(i,j) == 1:
            total += k
        else:
            for t in range(1,k+1):
                total += gcds(i,j,t)
print(total)
### BUGGY CODE ###


def solve():
	n=input()
	s='7'*len(n)
	flag=1
	i=len(n)
	if(int(n)%2==0):
		print(-1)
		return
	while(flag):
		if(int(s)%int(n)==0):
			flag=0
		else:
			i+=1
			s='7'*i
	print(len(s))
if __name__ == "__main__":
	#code goes below
	# for _ in range(int(input())):
	solve()

### FIXED CODE ###


def solve():
	n=int(input())
	if n%2==0 or n%5==0:
		print(-1)
		return 
	ans=1
	p=7%n
	while(p!=0):
		p=(p*10+7)%n
		ans+=1
	print(ans)
if __name__ == "__main__":
	#code goes below
	# for _ in range(int(input())):
	solve()
### BUGGY CODE ###

from functools import lru_cache

K = int(input())
sum = 0

@lru_cache()
def gcd(x,y):
  r = x % y
  while r> 0:
    x = y
    y = r
    r = x%y
  return y
  
for a in range(K):
  for b in range(K):
    for c in range(K):
      sum += gcd(gcd(a+1,b+1),c+1)
print(sum)

### FIXED CODE ###

from functools import lru_cache
@lru_cache()
def gcd(x,y):
    r = x%y
    if r == 0:
        return y
    return gcd(y,r)

K = int(input())
Sum = 0

for i in range(1,K+1):
    Sum += i
    for j in range(i+1,K+1):
        Sum += 6*gcd(i,j)
        for k in range(j+1,K+1):
            Sum += 6*gcd(gcd(i,j),k)
print(Sum)
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from bisect import bisect_left  as bl
from bisect import bisect_right as br
from bisect import insort_left  as il    # insort_leftはO(N)
from bisect import insort_right as ir
#-------------------------------------------------------------------
n = int(input())
L = list( map(int, input().split()) )	# 1 2 3 4 5 ...

L.sort()

ans=0


def bsl(L,c):
	rMax = len(L)-1
	
	l=0
	r=rMax
	
	if L[r]<c: return r+1
	
#	iCount=0
#	while iCount<=rMax:
#		iCount+=1

	while True:
		k=(l+r)//2
		#p("c,iCount,l,r,k ",c,iCount,l,r,k)
		
		if k==0: return k
		#if L[r]<=c: return r+1
		#p(20)
		if l+1==r: return r
		#p(30)
		if L[k-1]<c<=L[k]: return k
		#p(40)
		if L[k]<=c:
			l=k
		#	p(50)
			continue
		if c<L[k]:
			r=k
		#	p(60)
			continue
		#p(70)

#L=[1,3,5,7]
#for i in range(6,10):
#	print(i, bsl(L,i) )



for i in range(n-2):
	a=L[i]
	
	for j in range(i+1, n-1):
		b=L[j]
		
		#k = bl(L,a+b)
		k = bsl(L,a+b)
		
		ans+=k-j-1

print(ans)





### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from bisect import bisect_left  as bl
from bisect import bisect_right as br
from bisect import insort_left  as il    # insort_leftはO(N)
from bisect import insort_right as ir
#-------------------------------------------------------------------
n = int(input())
L = list( map(int, input().split()) )	# 1 2 3 4 5 ...

L.sort()

ans=0

for i in range(n-2):
	a=L[i]
	
	for j in range(i+1, n-1):
		b=L[j]
		
		k = bl(L,a+b)
		
		ans+=k-j-1

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

import sys

sys.setrecursionlimit(1000000)

def partition(A, p, r):
    i = p - 1
    for j in range(p, r + 1):
        if A[j] <= A[r]:
            i += 1
            A[i], A[j] = A[j], A[i]

    return i


def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)


n = int(raw_input())
A = map(int, raw_input().split())

quick_sort(A, 0, n - 1)

print " ".join(map(str, A))

### FIXED CODE ###

n = int(raw_input())
x = map(int,raw_input().split())
x.sort()
for i in xrange(n):
	print x[i],
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
ans = 0
for i in b:
    c = a.count(i)
    if c < i:
        ans += c
    if c > i:
        ans += c - i
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1
ans = 0
for i in d:
    if d[i] < i:
        ans += d[i]
    if d[i] > i:
        ans += d[i] - i
print(ans)