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

n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

A=[int(input()) for _ in range(int(input()))]
l=sorted(set(A))
cnt=0
for i in range(len(l)):
    if A.count(l[i])%2: cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
a={}
for _ in range(n):
    x=int(input())
    if x in a: a[x]+=1
    else: a[x]=1
ans=0
for i in a:
    if a[i]%2: ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]

i = 1
c = 0
while True:
    i = a[i - 1]
    c += 1
    if i == 1:
        c = -1
        break
    elif i == 2:
        break
print(c)


### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]

i = 1
c = 0
ans = -1
for _ in range(N):
    i = a[i - 1]
    c += 1
    if i == 2:
        ans = c
        break
print(ans)
### BUGGY CODE ###

while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if all([a[i+k]==P[k] for k in range(l)]):c+=1
	print c
	

### FIXED CODE ###

while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]==P:c+=1
	print c
### BUGGY CODE ###

S=input()
N=len(S)

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+(p*(10**i))%2019)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)


### FIXED CODE ###

S=input()
N=len(S)

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+ pow(10,i,2019)*p)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
lst = [ int(i) for i in input().split() ]
count = 0
for i in range(len(lst)):
    c = 0
    for j in range(i+1, len(lst)):
        c += lst[j]
    count += c * lst[i]
    
mod = 10**9 +7
if count >= mod:
    print(count%mod)
else:
    print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ruiseki = 0
count = 0
for i in range(n-1):
    ruiseki += a[i]
    count += ruiseki * a[i+1]
mod = 10**9 + 7
if count >= mod:
    print(count%mod)
else:
    print(count)
### BUGGY CODE ###

N = int(input())

S = input()

ans = 0

for i in range(N - 2):
    S_i = S[i]
    for j in range(i + 1, N - 1):
        if S[j] != S_i:
            S_j = S[j]
            for k in range(j + 1, N):
                if j - i != k - j and S[k] != S_i and S[k] != S_j:
                    ans += 1
print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans=S.count('R') * S.count('G') * S.count('B')
    for i in range(N):
        for d in range(N - 1):
            j = i + d
            k = j + d
            if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
    print(ans)
main()
### BUGGY CODE ###

from collections import deque
s=list(input())
n=len(s)
K=int(input())
d=deque()
l=[{} for _ in range(26)]
li=[]
cnt=0
st=""

for i in range(n):
    d.append(s[i])
#print(s,len(s))
for i in range(n):
    buf=deque()
    #print(s[i])
    piv=ord(s[i])-97
    for j in range(n-i):
        v=d.popleft()
        buf.append(v)
        st="".join(buf)
        l[piv][st]=cnt
    buf.popleft()
    d=buf
#print(l)
buf=[]
for i in range(26):
    #print(l[i],len(l[i]))
    if len(l[i])<K:
        K=K-len(l[i])
    else:
        buf = list(l[i])
        buf.sort()
        print(buf[K-1])
        break

### FIXED CODE ###

from collections import deque
s=list(input())
K=int(input())
#max(K)=5でaaaaaはa,aa,aaa,aaaa,aaaaaの順
#よって5文字まで取れば良い
d=deque()
for i in range(len(s)):
    d.append(s[i])
comp=[]
#print(d)
for i in range(len(s)):
    buf=deque()
    for j in range(len(d)):
        v=d.popleft()
        buf.append(v)
        if j<5:
            comp.append("".join(buf))
    d=deque()
    for j in range(len(buf)):
        d.append(buf[j])
    d.popleft()
comp=list(set(comp))
comp.sort()
print(comp[K-1])
### BUGGY CODE ###


def main(n,p):
  sheet=[min(i%n,i//n,n-i%n-1,n-i//n-1) for i in range(n**2)]
  space=[1]*(n**2)
  ans=0
  for x in p:
    x-=1
    ans+=sheet[x]
    space[x]=0
    todo=[(x,sheet[x])]
    while todo:
      v,c=todo.pop()
      x,y=divmod(v,n)
      for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        if 0<=x+dx<n and 0<=y+dy<n:
          nv=(x+dx)*n+(y+dy)
          if sheet[nv]>c:
            sheet[nv]=c
            todo.append((nv,c+space[nv]))
  print(ans)

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

### FIXED CODE ###

from numba import njit
import numpy as np
@njit
def dfs(v,c,h,stay):
    # hを更新
    x,y=divmod(v,n)
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx,ny=x+dx,y+dy
        if 0<=nx<n and 0<=ny<n:
            nv=nx*n+ny
            if h[nv]>c:
                h[nv]=c
                dfs(nv,c+stay[nv],h,stay)

@njit
def main(n,p):
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0

    for v in p:
        c=h[v]
        ans+=c
        stay[v]=0
        dfs(v,c,h,stay)
    print(ans)

    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    n=int(input())
    p=np.array(list(map(int,input().split())),np.int32)
    p-=1
    main(n,p)
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

def sieve(n=10**7):
    srn = int(n ** 0.5) + 1
    f = [True] * (srn + 1)
    res = []
    for i in range(2, srn+1):
        if not f[i]:
            continue
        res.append(i)
        for j in range(i * i, srn+1, i):
            f[j] = False
    return res

def trial_division(n):
    num = dict()
    for p in pn:
        while n % p == 0:
            num[p] = num.get(p, 0) + 1
            n //= p
    if n > 1:
        num[n] = 1
    res = 1
    for v in num.values():
        res *= (v + 1)
    return res

N = int(input())
pn = sieve(N)
res = sum(i * trial_division(i) for i in range(1, N+1))
print(res)


### FIXED CODE ###

N = int(input())
res = 0
for i in range(1, N+1):
    j = N // i
    res += j * (j + 1) // 2 * i
print(res)
### BUGGY CODE ###

from collections import defaultdict

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 size(self, x):
    return -self.parents[self.find(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]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
CD = [list(map(int, input().split())) for _ in range(k)]

fre = defaultdict(set)
for a, b in AB:
  fre[a - 1].add(b - 1)
  fre[b - 1].add(a - 1)

blo = defaultdict(set)
for c, d in CD:
  blo[c - 1].add(d - 1)
  blo[d - 1].add(c - 1)

#print(fre)
#print(blo)

uf = UnionFind(n)
for a, b in AB:
  uf.union(a-1, b-1)
#print(uf)
print(*[len(set(uf.members(i)) - fre[i] - blo[i]) - 1 for i in range(n)])

### FIXED CODE ###

from collections import defaultdict

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 size(self, x):
    return -self.parents[self.find(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]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
CD = [list(map(int, input().split())) for _ in range(k)]

uf = UnionFind(n)
fre = [0] * n
for a, b in AB:
  fre[a - 1] += 1
  fre[b - 1] += 1
  uf.union(a - 1, b - 1)

blo = [0] * n
for c, d in CD:
  if uf.same(c - 1, d - 1):
    blo[c - 1] += 1
    blo[d - 1] += 1

rs = uf.roots()
cnt = {r: uf.size(r) for r in rs}

ans = []
for i in range(n):
    r = uf.find(i)
    ans.append(cnt[r] - fre[i] - blo[i] - 1)
print(*ans)
### BUGGY CODE ###

import numpy as np
from itertools import combinations
n,k = map(int,input().split())
if n==1:
    print(int(input()))
else:
    lis = input().split()
    total =np.inf

    for i in combinations(lis,k):
        ml =0

        for a in i:

            ml += int(a)

        total = min(total,ml)


    print(total)

### FIXED CODE ###

n,k = map(int,input().split())
if n==1:
    print(int(input()))
else:
    total = 0
    lis = list(map(int,input().split()))
    lis.sort()
    for i in range(k):
        total += lis[i]
    print(total)
### BUGGY CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

d=defaultdict(list)
n,m,p=map(int,input().split())

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])

def BELLMANFORD(point,d,p):
    cost       = {node:-float("inf") for node in range(1,n+1)}
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


n,m,p=map(int,input().split())

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

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

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xi, hi = map(int, input().split())
    xh.append([xi, hi])

xh.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(xh[i][0])
    h.append(xh[i][1])

cnt = 0
for i in range(n):
    xi, hi = x[i], h[i]
    if hi == 0:
        continue
    else:
        num = (hi+a-1)//a
        cnt += num
    point = xi + 2*d
    left = i
    right = n
    while left+1 < right:
        mid = (left+right)//2
        if x[mid] <= point:
            left = mid
        else:
            right = mid
    for j in range(i, left+1):
        h[j] = max(0, h[j]-num*a)
print(cnt)

### FIXED CODE ###

n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

# 攻撃に巻き込めるインデックスを求める
left = 0 # 可能
right = n # 不可能
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = [0 for i in range(n)]
left = 0
already = 0
for i in range(n):
    while x[makikomi[left]] < x[i]:
        already -= cnt[left]
        left += 1
    cnt[i] = max(h[i] - already, 0)
    already += cnt[i]

print(sum(cnt))
### BUGGY CODE ###

def main():
    H, W = list(map(int, input().split()))
    A = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                pass
            else:
                if w == 0:
                    L[h][w] = 1
                else:
                    L[h][w] = L[h][w - 1] + 1
    for h in range(H):
        for w in range(W - 1, -1, -1):
            if A[h][w] == '#':
                pass
            else:
                if w == W - 1:
                    R[h][w] = 1
                else:
                    R[h][w] = R[h][w + 1] + 1
    for w in range(W):
        for h in range(H):
            if A[h][w] == '#':
                pass
            else:
                if h == 0:
                    U[h][w] = 1
                else:
                    U[h][w] = U[h - 1][w] + 1
    for w in range(W):
        for h in range(H - 1, -1, -1):
            if A[h][w] == '#':
                pass
            else:
                if h == H - 1:
                    D[h][w] = 1
                else:
                    D[h][w] = D[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
def main():
    printl = lambda l: [print(x) for x in l]
    H, W = list(map(int, input().split()))
    A = np.array([[1 if i == '.' else 0 for i in input()] for _ in range(H)])
    L = np.zeros((H, W), dtype = np.int)
    R = np.zeros((H, W), dtype = np.int)
    U = np.zeros((H, W), dtype = np.int)
    D = np.zeros((H, W), dtype = np.int)
    L[:, 0] = A[:, 0]
    for w in range(1, W):
        L[:, w] = (L[:, w - 1] + 1) * A[:, w]
    R[:, W - 1] = A[:, W - 1]
    for w in range(W - 2, -1, -1):
        R[:, w] = (R[:, w + 1] + 1) * A[:, w]
    U[0, :] = A[0, :]
    for h in range(1, H):
        U[h, :] = (U[h - 1, :] + 1) * A[h, :]
    D[H - 1, :] = A[H - 1, :]
    for h in range(H - 2, -1, -1):
        D[h, :] = (D[h + 1, :] + 1) * A[h, :]
    print(np.max(L + R + U + D - 3))

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

k = int(input())

ans = []

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

from itertools import product

for (x1, x2, x3) in product(list(range(1, k+1)), repeat=3):
    ans.append(gcd(gcd(x1, x2), x3))

print(sum(ans))


### FIXED CODE ###

k = int(input())

ans = []

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = [
        gcd(gcd(a, b), c) 
            for a in range(1, k+1)
            for b in range(1, k+1)
            for c in range(1, k+1)
      ]
print(sum(ans))
### BUGGY CODE ###

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

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

memo = dict()

def pick_cake(picked):
    key = ','.join([str(p) for p in sorted(picked)])
    if key in memo:
        return memo[key]

    if len(picked) == M:
        memo[key] = sum([abs(sum([cakes[i][j] for i in picked])) for j in range(3)])
        return memo[key]

    answer = 0
    for i in range(N):
        if i in picked:
            continue
        answer = max(answer, pick_cake(picked + [i]))
    return answer

print(pick_cake([]))

### FIXED CODE ###

from itertools import product

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

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

def _eval1(op):
    def _eval2(x):
        return eval(''.join(['{}{}'.format(op[i], x[i]) for i in range(3)]))

    return _eval2

answer = 0
for op in product('+-', repeat=3):
    answer = max(answer, sum([abs(sum([cake[j] for cake in sorted(cakes, key=_eval1(op))[:M]])) for j in range(3)]))

print(answer)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[0]*60
C=[0]*60
ans=0
mod=10**9+7
for i,a in enumerate(A):
  for j in range(60):
    if a%2==0:
      C[j]+=B[j]
    else:
      C[j]+=i-B[j]
      B[j]+=1
    a//=2
for i in range(60):
  ans=(ans+C[i]*(2**i))%mod
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[0]*60
C=[0]*60
ans=0
mod=10**9+7
for i,a in enumerate(A):
  for j in range(60):
    if a%2==0:
      C[j]+=B[j]
    else:
      C[j]+=i-B[j]
      B[j]+=1
    a//=2
for i in range(60):
  ans=(ans+C[i]*(pow(2,i,mod)))%mod
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
d=dict()
for i in range(1000):
  num='0'*(3-len(str(i)))+str(i)
  for j in range(n-2):
    if s[j]==num[0]:
      for k in range(j+1,n-1):
        if s[k]==num[1]:
          for l in range(k+1,n):
            if s[l]==num[2]:
              if num not in d:
                ans+=1
                d[num]=0
            if l==n-1:
              break
        if k==n-2:
          break
    if j==n-3:
      break
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for i in range(1000):
  l=(3-len(str(i)))*'0'+str(i)
  if l[0] in s:
    p1=s.index(l[0])
    if l[1] in s[p1+1:]:
      p2=p1+s[p1+1:].index(l[1])+1
      if l[2] in s[p2+1:]:
        cnt+=1
print(cnt)
### BUGGY CODE ###

from collections import deque

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

bar.sort()
bar = deque(bar)
ans = 0

while len(bar) > 1:
    a = bar.popleft()
    for i in range(len(bar)-1):
        b = bar[i]
        for j in range(i+1, len(bar)):
            c = bar[j]
            if c < (a+b):
                ans += 1
            else:
                break
print(ans)

### 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):
        T=bisect.bisect_left(L,L[i]+L[j])
        count += T-j-1

print(count)
### BUGGY CODE ###

N = int(input())
D = sorted(list(map(int, input().split())))

M = int(input())
T = sorted(list(map(int, input().split())))

# if N < M:
#     print('NO')
# else:
ind = 0
for t in T:
    for i,d in enumerate(D[ind:]):
        if d == t:
#            print(ind,D[ind:])
            ind += i + 1
            break
    else:
        print('NO')
        exit()
    if M - t > N - ind + 1:
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

import collections
N = int(input())
D = sorted(list(map(int, input().split())))

M = int(input())
T = sorted(list(map(int, input().split())))

DD = collections.Counter(D)
TT = collections.Counter(T)
ch = 1
for t,num_t in TT.items():
    num_d = DD[t]
    if num_t > num_d:
        ch = 0

if ch == 1:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import itertools
import numpy as np
cost = 10**12
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
combi = itertools.permutations(range(N),N)
for a in combi:
    x = np.array([0]*M)
    fx = np.array([0]*M)
    c = 0
    for i in range(len(a)):
        x += ca[a[i]][1:]
        c += ca[a[i]][0]
        if c>cost:
            break
        if sum(x>=X)==M:
            break
    if sum(x>=X)==M:
        cost = min(c,cost)
print(cost if cost !=10**12 else -1)


### FIXED CODE ###

import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)