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

n,w=map(int,input().split())
dp=[[0 for i in range(w+1)] for j in range(n+1)]
c,p=map(int,input().split())
dp[1][c]=p
for i in range(2,n+1):
  c,p=map(int,input().split())
  for j in range(w):
    if dp[i-1][j] != 0:
      dp[i][j]=dp[i-1][j]
  for j in range(w):
    if j+c<=w and dp[i-1][j] != 0:
      dp[i][j+c]=max(dp[i-1][j+c],dp[i-1][j]+p)
  dp[i][c]=max(dp[i-1][c],p)
print(max([dp[n][i] for i in range(w+1)]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))
### BUGGY CODE ###

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

p = [ k for _ in range(n) ]

for x in a:
	p[x-1] += 1
	p = [ y-1 for y in p ]

ans = []

for z in p:
	if z > 0:
		ans.append('Yes')
	else:
		ans.append('No')

for blah in ans:
	print(blah)

### FIXED CODE ###

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

p = [ k for _ in range(n) ]

p = [ y-q for y in p ]

for x in a:
	p[x-1] += 1

ans = []

for z in p:
	if z > 0:
		ans.append('Yes')
	else:
		ans.append('No')

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

H = int(input())
if H == 1:
    cnt = 1
else:
    J = list()
    J.append(H)
    cnt = 0
    while len(J) > 0:
        if J[0] == 1:
            del J[0]
            cnt += 1
        else:    
            J.append(J[0]//2)
            J.append(J[0]//2)
            del J[0]
            cnt += 1
print(cnt)

### FIXED CODE ###

import math
h = int(input())
hp = h
c = 0
ans = 0

while hp > 1:
    hp = math.floor(hp/2)
    c += 1
for i in range(0,c+1):
    ans += 2 ** i
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

# 1要素目: 最大の色(赤とする)の和
# 2要素目: i番目の整数までを考慮
# 3要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
dp = np.zeros(300*(N+1)**2*4, dtype=int).reshape(-1, N+1, 4)
dp[0, 0, 3] = 1

sum_a = 0
for i in range(1, N+1):
    a = d_in()
    sum_a += a
    # 赤に入れる
    dp[a:, i, :] += dp[:-a, i-1, :]

    # 緑に入れる
    dp[:, i, 0] += dp[:, i-1, 0]
    dp[:, i, 0] += dp[:, i-1, 2]
    dp[:, i, 1] += dp[:, i-1, 1]
    dp[:, i, 1] += dp[:, i-1, 3]

    # 青に入れる
    dp[:, i, 0] += dp[:, i-1, 0]
    dp[:, i, 0] += dp[:, i-1, 1]
    dp[:, i, 2] += dp[:, i-1, 2]
    dp[:, i, 2] += dp[:, i-1, 3]
    dp %= MOD


print((total - dp[(sum_a+1)//2:, -1, 0].sum() * 3) % MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    if i % 10 == 0:
        dp[i, :, :] %= MOD

print((total - dp[-1, 0, -1] * 3) % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from decimal import Decimal

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

Z = np.zeros((50,50), dtype=int)

def count2(a):
  n = a
  count = 0
  while n%2 == 0:
    n //= 2
    count += 1
  return count

def count5(a):
  n = a
  count = 0
  while n%5 == 0:
    n //= 5
    count += 1
  return count

answer = 0
for i in range(N):
  a = int(A[i]*10**9)
  c2 = count2(a)
  c5 = count5(a)
  t2 = max(18-c2,0)
  t5 = max(18-c5,0)
  if i>0:
    answer += np.sum(Z[t2:,t5:])
  Z[c2,c5] += 1

print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from decimal import Decimal

N = int(input())
A = [int(10**9*Decimal(input())) for _ in range(N)]

Z = np.zeros((20,20), dtype=int)

def count2(a):
  n = a
  count = 0
  while n%2 == 0:
    n //= 2
    count += 1
  return count

def count5(a):
  n = a
  count = 0
  while n%5 == 0:
    n //= 5
    count += 1
  return count

answer = 0
for a in A:
  c2 = count2(a)
  c5 = count5(a)
  t2 = max(18-c2,0)
  t5 = max(18-c5,0)
  #answer += np.sum(Z[t2:,t5:])
  #Z[min(19,c2),min(19,c5)] += 1
  answer += Z[t2,t5]
  Z[:min(19,c2)+1,:min(19,c5)+1] += 1

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

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    l = len(com)
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    elif com[6] == " ":
        C = com.split()
        x = int(C[1])
        try:
            L.remove(x)
        except:
            pass
    elif l > 10:
        L.popleft()
    else:
        L.pop()

print(*L)


### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.appendleft(query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1

ans = deque()

if rev % 2 == 1:
    s = ''.join(list(reversed(s)))


for i in range(len(d)):
    if d[i] == 'S':
        ans.append(s)
    else:
        ans.append(d[i])

print(*ans,sep='')

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')
### BUGGY CODE ###

N = input()
A = input().split()
ans = 1
for i in A:
    ans = ans * int(i)
    if ans == 0:
        break

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
A.sort()
ans = 1
for i in A:

    ans = ans * i
    if ans == 0:
        break
    if ans > 1000000000000000000:
        ans = -1
        break

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

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

from bisect import *

def f(a,b,k,cnta): #k桁目のxor
    p1 = 1<<k
    p2 = p1<<1
    p3 = p1+p2
    b = sorted(i&(p2-1) for i in b)
    
    res = 0
    if k > N:
        for ai in a:
            ai &= (p2-1)
            if p1 > b[0]: j1 = bisect_left(b,p1-ai)
            else: j1 = 0
            j2 = bisect_left(b,p2-ai)
            if p3 - ai > b[-1]: j3 = n
            else: j3 = bisect_left(b,p3-ai)
            res += j2-j1+n-j3
        return (res&1)<<k
    else:
        for ai,num in enumerate(cnta):
            if num == 0: continue

            ai &= (p2-1)
            if p1 > b[0]: j1 = bisect_left(b,p1-ai)
            else: j1 = 0
            j2 = bisect_left(b,p2-ai)
            if p3 - ai > b[-1]: j3 = n
            else: j3 = bisect_left(b,p3-ai)
            res += num*(j2-j1+n-j3)
            
            #print(res,cnta,b,p1,j1,j2,j3,n)
        return (res&1)<<k
            






N = 17
N2 = 1<<(N+1)
cnta = 0
#cntb = [0]*N2
#for i in b: cntb[i&N2] += 1

ans = 0
for k in range(28,-1,-1):
    if k == N:
        cnta = [0]*N2
        N2 -= 1
        for i in a: cnta[i&N2] += 1
    if k < N:
        cnta = [i+j for i,j in zip(cnta[:(1<<(k+1))],cnta[(1<<(k+1)):])]
    #print(cnta)
    ans |= f(a,b,k,cnta)

print(ans)    









### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

from bisect import bisect_left


ans = 0

for k in range(29):
    a0 = []
    a1 = []
    a0a = a0.append
    a1a = a1.append
    
    b0 = []
    b1 = []
    b0a = b0.append
    b1a = b1.append
    for i in a: #基数ソート
        if i&(1<<k): a1a(i)
        else: a0a(i)
    for i in b: #基数ソート
        if i&(1<<k): b1a(i)
        else: b0a(i)
    
    a = a0+a1
    b = b0+b1
    mask = (1<<(k+1))-1
    
    aa = [i&mask for i in a]
    bb = [i&mask for i in b]
    
    res = 0
    p1 = 1<<k
    p2 = mask+1
    p3 = p1+p2

    j1=j2=j3=0    
    for ai in reversed(aa):
        while j1 < n and ai+bb[j1] < p1:
            j1 += 1
        while j2 < n and ai+bb[j2] < p2:
            j2 += 1
        while j3 < n and ai+bb[j3] < p3:
            j3 += 1
        res += j2-j1+n-j3
        #if k < 3: print(ai,p2,res,bb,j1,j2,j3,n)
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    ans |= (res&1)<<k
    



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

import heapq
N, M = map(int, input().split())
S = [False] * N
G = [[] for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
loop = False
for i in range(M):
  l, r, d = map(int, input().split())
  G[l - 1].append([r - 1, d])
for i in range(N):
  if not S[i] and G[i]:
    _X = [None for i in range(N)]
    _X[i] = 0
    Q = []
    heapq.heappush(Q, [0, i])
    contract = False
    while Q:
      s = heapq.heappop(Q)
      S[s[1]] = True
      for adj, d in G[s[1]]:
        if _X[adj] == None:
          _X[adj] = s[0] + d
          if _X[adj] <= 10 ** 9:
            heapq.heappush(Q, [_X[adj], adj])
          else:
            contract = True
            break
        elif _X[adj] != s[0] + d:
          contract = True
          break
      if contract:
        break
    if contract:
      print('No')
      break
else:
  print('Yes')

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
S = [0] * N
for _ in range(M):
  l, r, d = map(int, input().split())
  S[l - 1] = 1
  E[l - 1].append([d, r - 1])
  RE[r - 1].append([d, l - 1])
D = [None] * N
def dijkstra(i):
  D[i] = 0
  Q = [[0, i]]
  while Q:
    d, s = heapq.heappop(Q)
    for dist, adj in E[s]:
      if D[adj] == None:
        D[adj] = D[s] + dist
        heapq.heappush(Q, [D[adj], adj])
      elif D[adj] == 'Error' or D[adj] != D[s] + dist:
        D[s] = 'Error'
        break
    else:
      for dist, adj in RE[s]:
        if D[adj] == None:
          D[adj] = D[s] - dist
          heapq.heappush(Q, [D[adj], adj])
        elif D[adj] == 'Error' or D[adj] != D[s] - dist:
          D[s] = 'Error'
          break
      else:
        continue
    break
for i in range(N):
  if D[i] == 'Error':
    print('No')
    break
  elif D[i] == None:
    dijkstra(i)
else:
  for d in D:
    if d == 'Error':
      print('No')
      break
  else:
    print('Yes')
### BUGGY CODE ###

def f(): return map(int,raw_input().split())
n,q=f()
A=[[0,-i] for i in range(n+1)]
for _ in range(q):
  a,b=f()
  A[a][0]+=b
  m0,m1=sorted(A,key=lambda A:[A[0],A[1]])[-1]
  print -m1,m0

### FIXED CODE ###

def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  if a==a0 and v<0:
    v0=max(A)
    a0=A.index(v0)
  elif A[a]>v0: a0,v0=a,A[a]
  elif A[a]==v0 and a<a0: a0=a
  print a0,v0
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(n)
    C = [input().split(" ") for i in range(n)]
    C = map(lambda x:(x[0], getNum(x[1])), C)
    
    for command, num in C:
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

n=int(input()) #get input N
a=list(map(int, input().split())) #get input A
b=1 #first to multiply

for i in a:#multiply all list in A
    b*=i

if b>1000000000000000000: #if more than 10^18
    print("-1")

else: 
    print (b)

### FIXED CODE ###

# we collect the input A1 upto An.
# limit cannot exceed 10**18
# if N = 0 then ans = 0
# in N is in range then compute ans * A[n]
# else if  ans is greater than limit then display 1
# finally if length equal 1 then display -1
N = int(input())
ans = 1
limit = 10 ** 18
length = 0

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

A0 = set(A)
if 0 in A0:
    ans = 0
else:
    pass

for n in range(N):
    ans = ans * A[n]
    if ans == 0:
        break
    elif ans > limit:
        length = 1
        break
    else:
        pass

if length == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
import collections
import math
from collections import Counter
from collections import deque


N, M = [int(x) for x in input().split()]

scc = 0
n = N
m = M

while (n >= 1 and m >= 2):
    n -= 1
    m -= 2
    scc += 1
if m >= 4:
    scc += (m // 4)

print(scc)

sys.exit(0)


### FIXED CODE ###

import sys
import collections
import math
from collections import Counter
from collections import deque


N, M = [int(x) for x in input().split()]

scc = 0
n = N
m = M

scc = min(n, m // 2)

n = n - scc
m = m - 2 * scc

if m >= 4:
    scc += (m // 4)

print(scc)
sys.exit(0)
### BUGGY CODE ###

r = []
N = int(input())
for i in range(0, N):
    r.append(int(input()))

min_i = N-2
max_i = N-1

for i in range(N-1)[::-1]:
    if (r[i] - r[i+1]) * r[max_i] - r[min_i] < 0:
        for j in range(i+1, N):
            if r[j] - r[i] > r[max_i] - r[min_i]:
                max_i = j
                min_i = i

                
print(r[max_i] - r[min_i])

### FIXED CODE ###

N = int(input())
r = [int(input()) for i in range(N)]
 
min = r[0]
max = -9999999999999999
 
for i in range(1, N):
    if r[i] - min > max:
        max = r[i] - min
    if r[i] < min:
        min = r[i]
 
print(max)
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
w=[x[-1]]
for y in x[N-2::-1]:w+=[w[-1]+y]
r=1e20
for k in range(1,N+1):
    s=0
    for j in range(1,1+((N+k-1)//k)):
        s+=max(5,2*j+1)*(w[min(N,k*j)-1]-(0 if j==1 else w[k*j-k-1]))
    s+=(N+k)*X
    r=min(s,r)
print(r)

### FIXED CODE ###

N,X=map(int,input().split())
w=[0]
for i in map(int,input().split()):w+=[w[-1]+i]
print(min(5*w[N]+k*X+sum(2*w[j]for j in range(N-k*2,0,-k))for k in range(1,N+1))+N*X)
### BUGGY CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=np.array(n)
max=0
for i in range(N-K+1):
    tmp = np.sum(n[i:i+K]) 
    if tmp  > max:
        max=tmp 

print((max+K)*0.5)

### FIXED CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=(n+1)
t=np.empty(N+1)
t[0] = 0
t[1:]=np.cumsum(n)
print(max(t[K:]-t[:-K])*0.5)
### BUGGY CODE ###

S=input()
N=len(S)
from collections import defaultdict
O=defaultdict(int)
O[5]=1
mod=10**9+7
for i in range(N):
    On=defaultdict(int)
    for o in O.keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    On[x//10]+=O[o]
        else:
            for j in range(10):
                x=13*j+o
                On[x//10]=(On[x//10]+O[o])%mod
    O=On
print(O[0])

### FIXED CODE ###

S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])
### BUGGY CODE ###

N=input()
A=list(map(int,input().split()))
ans=0
M=10**9+7
for i in range(len(A)-1):
    for j in range(len(A)-i-1):
        ans+=A[i]*A[i+j+1]%M
        ans%=M
print(ans)

### FIXED CODE ###

N=input()
A=list(map(int,input().split()))
ans=0
S=sum(A)
M=10**9+7
for i in A:
    S-=i
    ans+=i*S%M
    ans%=M
print(ans)
### BUGGY CODE ###

import heapq

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

heapq.heapify(A)

for _ in range(M):
    b,c=list(map(int,input().split()))

    i=0
    while i<b:
        a=heapq.heappop(A)

        if a>=c:
            heapq.heappush(A,a)
            break

        heapq.heappush(A,c)
        i+=1

print(sum(A))


### FIXED CODE ###

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

D=[0]*N
i=0
for b,c in bc:
    cnt=0
    while i<N and cnt<b:
        D[i]=c
        i+=1
        cnt+=1
    if i==N:
        break

E=[max(A[i],D[i]) for i in range(N)]
print(sum(E))
### BUGGY CODE ###

import itertools
n,*l=map(int,open(0).read().split())
print(sum(a<b+c and b<c+a and c<a+b for a,b,c in itertools.combinations(l, 3)))

### FIXED CODE ###

import bisect
n,*l=map(int,open(0).read().split())
l.sort()
a=0
for i in range(n):
    for j in range(i+1,n):
        k=l[i]+l[j]
        a+=max(0,bisect.bisect_left(l,k)-j-1)
print(a)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n].append(node)
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)



    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        length = len(stack[tree])
        for k in stack[tree]:
            candidates[k] = length - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()