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

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

pList = list(map(int,input().split()))

cList = list(map(int,input().split()))

cSum = sum(cList)
p = {}
c = {}

for i in range(n):
    p[i] = pList[i]
    c[i] = cList[i]

highScore = min(cList)
for i in range(n):
    count = 0
    zahyou = i
    score = 0
    zumi =set()
    loop = False
    while count < k:
        if not(loop):
            if zahyou in zumi:
                loop = True
                if score > 0:
                    score += score * ((k // count) - 2)
                    count += ((k // count) - 2) * count
                else:
                    break
        zumi.add(zahyou)
        zahyou = p[zahyou] - 1
        score += c[zahyou]
        count += 1
        if highScore < score:
            highScore = score

print(highScore)

### FIXED CODE ###

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

pList = list(map(int,input().split()))

cList = list(map(int,input().split()))

cSum = sum(cList)
p = dict()
c = dict()

for i in range(n):
    p[i] = pList[i]
    c[i] = cList[i]

highScore = min(cList)
for i in range(n):
    count = 0
    zahyou = i
    score = 0
    zumi =zahyou
    loop = False
    while count < k:
        if not(loop):
            if zahyou == zumi and count != 0:
                loop = True
                if score > 0:
                    score += score * ((k // count) - 2)
                    count += ((k // count) - 2) * count
                else:
                    break
        zahyou = p[zahyou] - 1
        score += c[zahyou]
        count += 1
        if highScore < score:
            highScore = score

print(highScore)
### BUGGY CODE ###

N = int(input())
S = '0'
S += input()
R_count = 0
G_count = 0
B_count = 0
for i in range(1, N + 1):
  if S[i] == 'R':
    R_count += 1
  if S[i] == 'G':
    G_count += 1
  if S[i] == 'B':
    B_count += 1
res = R_count * G_count * B_count
for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    if 2 * j - i > N:
      break
    temp = []
    temp += S[i] + S[j] + S[2 * j - i]
    temp.sort()
    if temp[0] == 'B' and temp[1] == 'G' and temp[2] == 'R':
      res -= 1
print(res)

### FIXED CODE ###

N = int(input())
S = '0'
S += input()
R_count = 0
G_count = 0
B_count = 0
for i in range(1, N + 1):
  if S[i] == 'R':
    R_count += 1
  if S[i] == 'G':
    G_count += 1
  if S[i] == 'B':
    B_count += 1
res = R_count * G_count * B_count
for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    if 2 * j - i > N:
      break
    temp = []
    temp += S[i] + S[j] + S[2 * j - i]
    temp.sort()
    if temp[0] == 'B' and temp[1] == 'G' and temp[2] == 'R':
      res -= 1
print(res)
### BUGGY CODE ###

N = int(input())
a_s = input().split(" ")
a_s = list(map(int, a_s))

mod = 10**9 +7
ans = 0
for i in range(len(a_s)-1):
  for j in range(i+1, len(a_s)):
    ans += ((a_s[i]*a_s[j])%mod)
    if ans > mod:
      ans = ans%mod
      
print(ans)

### FIXED CODE ###

N = int(input())
a_s = input().split(" ")
a_s = list(map(int, a_s))
asum = sum(a_s)

mod = 10**9 +7
ans = 0
for i in range(len(a_s)-1):
  asum -= a_s[i]
  ans += (asum*a_s[i])%mod
  if ans > mod:
    ans = ans%mod
      
print(ans)
### BUGGY CODE ###

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

while M > 0:
    A.sort()
    tmp = A.pop(-1)
    tmp = tmp//2
    M -= 1
    A.append(tmp)
    
print(sum(A))

### FIXED CODE ###

from heapq import heappop,heappush,heapify
 
N,M = map(int,input().split())
A = [int(x) for x in input().split()]
 
A_minus = [-x for x in A]

# priority queue を使う
# 最小値を取り出す、要素を挿入する
heapify(A_minus)

for _ in range(M):
    tmp_min = heappop(A_minus)
    tmp_min = (-1)*(-tmp_min//2)
    heappush(A_minus,tmp_min)
    
print(-sum(A_minus))
### BUGGY CODE ###

h, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append([a, b])

dp = [10 ** 8 + 1 for i in range(h+1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    y = max(i-l[j][0], 0)
    if dp[i] > l[j][1] + dp[y]:
      dp[i] = l[j][1] + dp[y]


print(dp[h])


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

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

if n%2==1:
    for i in range(n):
        if i%2==1:
            b.append(a[i])
        else:
            b.insert(0,a[i])

else:
    for i in range(n):
        if i%2==0:
            b.append(a[i])
        else:
            b.insert(0,a[i])

print(*b)


### FIXED CODE ###

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

if n%2==0:

    for i in range(n):

        if n-i*2-1 > 0:
            b.append(a[n-i*2-1])
        else:
            k=abs(n-i*2)
            b.append(a[k])

else:
    
    for i in range(n):

        if n-i*2-1 >= 0:
            b.append(a[n-i*2-1])
        else:
            k=abs(n-i*2-1)
            b.append(a[k-1])

print(*b)
### BUGGY CODE ###

import sys

h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=s.count("#")

dist=[[False]*w for i in range(h)]
done=[[float('inf')]*w for i in range(h)]

cnt=0
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    dist[y][x]=True
    
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]

    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or dist[my][mx]==True:
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
    
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)

if __name__=="__main__":
  bfs()

### FIXED CODE ###

import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("#") for j in s)
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or done[my][mx]!=float('inf'):
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

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

A.sort(reverse=True)
cnt = 1
A[0]=A[0]//2

if N==1:
    while A[0]>0 and cnt<M:
        cnt+=1
        A[0]=A[0]//2
else:
    while cnt<M:
        while A[0]>=A[1] and cnt<M:
            cnt+=1
            A[0]=A[0]//2
        if cnt==M:break
        else:
            b=A[0]
            for i in range(1,N):
                if A[i]>b:A[i-1]=A[i]
                else:
                    A[i-1]=b
                    break
    
print(sum(A))
    
        

### FIXED CODE ###

import heapq

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

a = [-int(x) for x in input().split()]

heapq.heapify(a)

num = 0
hq = 1

while num < M and hq != 0:
    hq = -heapq.heappop(a)
    hq2 = hq // 2
    heapq.heappush(a, -hq2)
    num += 1

print(-sum(a))
### BUGGY CODE ###

n = int(input())
r = [None] * n
min = 10**10
max = -10**10
for i in range(n):
    r[i] = int(input())

for i in range(n):
    if min > r[i]:
        min = r[i]
        for j in range(i+1,n):
            if max < r[j] - min:
                max = r[j] - min
print(max)

### FIXED CODE ###

n = int(input())
minv = int(input())
maxv = (10**9)*(-1)
for j in range(1,n):
    r = int(input())
    if maxv < (r - minv):
        maxv = r - minv
    if minv > r:
        minv = r
print(maxv)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

# identity element
ide_ele = 10**9+1
 
def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))
 
    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y
 
    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
 
    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])
 
    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res
 
    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num
 
    init(A)
 
    ans = 10**18
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += min(query(i-k, i-k//2), query(i-k//2, i+1))
            else:
                temp1 = min(query(0, i//2), query(i//2, i+1))
                temp2 = min(query(n-(k-i), n-(k-i)//2), query(n-(k-i)//2, n))
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

N=input()
A=list(map(int,input().split()))
ans = []
for i in range(min(A),max(A)+1):
    ans.append(A.count(i-1)+A.count(i)+A.count(i+1))
print(max(ans))

### FIXED CODE ###

input()
A=list(map(int,input().split()))
c=[0 for _ in range(10**5+3)]
for a in A:
    c[a]+=1
    c[a-1]+=1
    c[a+1]+=1
print(max(c))
### BUGGY CODE ###

S = str(input())
a = 1
count=0
while True:
    a = S.count("BW")
    count+=a
    if S == S.replace("BW","WB"):
        break
    else:
        S = S.replace("BW","WB")
print(count)

### FIXED CODE ###

S = str(input())
slist = list(S)
L = len(slist)
count = 0
fcount = 0
for i in range(L):
  if slist[i] == "W":
    count+=(i-fcount)
    fcount+=1
print(count)
### BUGGY CODE ###

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

d=[0]*(10**5 +1 )

for i in a:
    d[i-1]+=i

for _ in range(q):
    b,c=map(int,input().split())
    ans=0
    k=d[b-1]//b
    d[c-1]+=c*k
    d[b-1]=0

    print(sum(d))


### FIXED CODE ###

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

s=sum(a)
d=[0]*(10**5+1)
for i in a:
    d[i-1]+=1

for _ in range(q):
    b,c=map(int,input().split())
    tmp=0
    k=d[b-1]
    d[c-1]+=k
    d[b-1]=0

    tmp = k*c-k*b
    s+=tmp
    print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

    for _ in range(K):
        B = [0]*N
        for i, a in enumerate(A):
            bottom = max(0, i-a)
            top = min(N, i+a+1)
            # B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
            B[bottom] += 1
            if top < N:
                B[top] -= 1
        for j in range(1, N):
            B[j] += B[j-1]

        if A == B:
            A = B[:]
            break
        A = B[:]

    ans = ' '.join(list(map(str, A)))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


@jit
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


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

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = []

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC' and p not in ac_done:
        ac += 1
        wa += l[p-1]
        ac_done.append(p)
    else:
        l[p-1] = 1 + l[p-1]

print(ac,wa)

### FIXED CODE ###

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = [False] * n

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if ac_done[p-1]:
        continue
    else:
        if s == 'AC':
            ac += 1
            wa += l[p-1]
            ac_done[p-1] = True
        else:
            l[p-1] += 1 

print(ac,wa)
### BUGGY CODE ###

try:
    (m,n)  =  map(int,input().split())
except:
    exit

r = pow(m,n) %  1000000007
print (r)


### FIXED CODE ###

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

bi = str(format(n,"b"))
bi = bi[::-1]

c = 1
d = 1000000007

for i in bi:
    if ( i == "1"):
        c = ( c * m ) % d
    m = (m * m) %d
print (c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
out = [0] * n
count = 0
out_str = ""
for j in range(n):
    for i in range(n):
        if j + 1 == a[i]:
            out[j] = i + 1
            break

for i in range(n):
    out_str = out_str + str(out[i]) + " "

print(out_str[:-1])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
out = [""] * n
out_str = ""
for i in range(n):
    out[a[i] - 1] = str(i + 1)
        
out_str = " ".join(out)
 
print(out_str)
### BUGGY CODE ###

N=int(input())
S=str(input())
count=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if j-i!=k-j and S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=list(str(input()))
r=S.count('R')
g=S.count('G')
b=S.count('B')
count=0

for i in range(int((N-3)/2)+1):
    for k in range(N-i*2-3+1):
        if S[k]!=S[k+i+1] and S[k]!=S[k+2*i+2] and S[k+i+1]!=S[k+2*i+2]:
            count+=1
print(r*g*b-count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[N-1][i] = 1
            dp[i][N-1] = 1

    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1

    res = 0
    for i in range(N):
        for j in range(i+1,N):
            l = dp[i][j]
            if j >= i+l:
                res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

import re
def resolve():
    inp = input()
    result = inp

    while True:
        before = len(result)
        result = re.sub(r'01|10', '', result)
        after = len(result)
        if before == after:
            break

    print(len(inp)-len(result))

resolve()


### FIXED CODE ###

def resolve():
    inp = input()

    c0 = inp.count('0')
    c1 = inp.count('1')

    print(min(c0, c1)*2)

resolve()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s="YES"
for i in range(n):
    for j in range(i+1,n):
        if a[i]==a[j]:
            s="NO"
            break
print(s)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
s="YES"
for i in range(n-1):
    if a[i]==a[i+1]:
        s="NO"
        break
print(s)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    S = input()
    # 再帰的に解いて解く

    @lru_cache(None)
    def solver(T):
        if T == "":
            print("YES")
            quit()
        if len(T) >= 5:
            if T[:5] == "dream" or T[:5] == "erase":
                solver(T[5:])
        if len(T) >= 6:
            if T[:6] == "eraser":
                solver(T[6:])
        if len(T) >= 7:
            if T[:7] == "dreamer":
                solver(T[7:])
        return

    solver(S)
    print("NO")
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    S = input()
    # 後ろから貪欲に評価すればよい
    while True:
        if S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue
        elif S[-6:] == "eraser":
            S = S[:-6]
            continue
        elif S[-7:] == "dreamer":
            S = S[:-7]
            continue
        else:
            break
    if S == "":
        print("YES")
    else:
        print("NO")
    return


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

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

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

ln.sort(reverse=True)

bcs = []
for i in range(1, n-1):
  row = []
  for j in range(i+1, n):
    row.append(ln[i] + ln[j])
  bcs.append(row)

cnt = 0
ix = [0 for _ in range(n-2)]
# a > b,c
for i in range(n-2):
  a = ln[i]
  for j in range(i, n-2):
    try:
      while ix[j] < (n - 2 - j) and bcs[j][ ix[j] ] > a:
        ix[j] += 1
    except:
      print(j, ix[j])
      exit()
  cnt += sum(ix[i:])
print(cnt)

### FIXED CODE ###

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

ln.sort(reverse=True)

bcs = []
for i in range(1, n-1):
  row = []
  for j in range(i+1, n):
    row.append(ln[i] + ln[j])
  bcs.append(row)

cnt = 0
ix = [0 for _ in range(n-2)]
# a > b,c
for i in range(n-2):
  a = ln[i]
  for j in range(i, n-2):
    try:
      while ix[j] < (n - 2 - j) and bcs[j][ ix[j] ] > a:
        ix[j] += 1
    except:
      print(j, ix[j])
      exit()
  cnt += sum(ix[i:])
print(cnt)
### BUGGY CODE ###

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

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])

AB.sort(reverse=True)
#print(AB)
AB = AB[:K]

ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i] + C[j])
        
ABC.sort(reverse=True)
ABC = ABC[:K]

for i in ABC:
    print(i)

### FIXED CODE ###


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

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

sum = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            if (x+1)*(y+1)*(z+1) <= K:
                sum.append(A[x] + B[y] + C[z])
            else:
                break

sum.sort(reverse=True)
for i in range(K):
    print(sum[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
lim = 10**18
ans = 1
for i in range(n):
  ans = ans*a[i]

if ans > lim:
  ans = -1
    
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
b = np.sqrt(a)

lim = 10**9
lim_1 = 10**18
ans_1 = np.prod(b)
ans = np.prod(a)

if ans_1 > lim:
  ans = -1
elif ans_1 < 0:
  ans = -1
    
if ans > lim_1:
  ans = -1
elif ans < 0:
  ans = -1
  
print(ans)
### BUGGY CODE ###

import fractions
k = int(input())
ans = k**3 - (k-1)**3
for a in range(2,k+1):
  for b in range(2,k+1):
    for c in range(2,k+1):
      ans += fractions.gcd(a, fractions.gcd(b, c))
print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = k**3 - (k-1)**3
for a in range(2,k+1):
  for b in range(2,k+1):
    tmp = math.gcd(a,b)
    for c in range(2,k+1):
      ans += math.gcd(tmp, c)
print(ans)
### BUGGY CODE ###


n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in xrange(n + 1):
    dp[i][0] = 0
for i in xrange(1, n + 1):
    wi, vi = items[i - 1]

    for j in range(1, vi):
        dp[i][j] = dp[i - 1][j]

    for j in range(vi, v + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j], wi + dp[i - 1][j - vi])
for i in xrange(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break


### FIXED CODE ###


n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in xrange(n + 1):
    dp[i][0] = 0
for i in xrange(1, n + 1):
    wi, vi = items[i - 1]

    for j in range(1, vi):
        dp[i][j] = dp[i - 1][j]

    for j in range(vi, v + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j], wi + dp[i - 1][j - vi])
for i in xrange(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break
### BUGGY CODE ###

n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            c = tris[mid]
            if a < b + c and b < c + a and c < a + b:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        r = bisect.bisect_left(tris, a+b)
        cnt += r - j - 1
print(cnt)