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

def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(10):
        for k in range(13):
          dpi1[(k * 10 + j) % 13] += dpi[k]
    else:
      t = int(s[i])
      for k in range(13):
        dpi1[(k * 10 + t) % 13] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

from itertools import permutations
n = int(input())
A = [int(input()) for _ in range(n)]
def f(x):
    cnt = 0
    for i in range(len(x) - 1):
        cnt += abs(x[i] - x[i + 1])
    return cnt
ans = []
for B in permutations(A):
    ans.append((f(B), B))
ans.sort(reverse=True)
print(ans[0][0])


### FIXED CODE ###

def solve():
    n = int(input())
    a = sorted(int(input()) for _ in range(n))
    c0 = n // 2 - 1
    c1 = n // 2
    c2 = n // 2 + 1
    ans = 0
    if n & 1:
        for i in range(c0):
            ans -= a[i] * 2
        for i in range(c2 + 1, n):
            ans += a[i] * 2
        ans += -a[c0] + a[c2] + max(-a[c0] + a[c1], - a[c1] + a[c2])
    else:
        for i in range(c0):
            ans -= a[i] * 2
        for i in range(c1 + 1, n):
            ans += a[i] * 2
        ans += -a[c0] + a[c1]
    return ans
print(solve())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

def solve_even(a, n):
  s = sum(a[::2])
  ans = s
  i = n - 2
  while i >= 0:
    s += a[i+1] - a[i]
    ans = max(ans, s)
    i -= 2
  return ans

def solve_odd(a, n):
  if n == 1:
    return 0
  ans = solve_even(a[:-1], n-1)
  s = a.pop()
  a.pop()
  ans = max(ans, s + solve_odd(a, n-2))
  return ans
  

if N%2 == 0:
  print(solve_even(A, N))
else:
  print(solve_odd(A, N))

### FIXED CODE ###

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

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

import sys
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs = []
ts = set()
qs = []
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
for _ in range(Q):
    xs.append((int(input()), 2, 0))
xs.sort(key=lambda x:x[0])
xs += [(10**9,True,x)]

mx = max(ts) + 1
tmp = list(ts)
x2i = dict()
for i, x in enumerate(ts):
    x2i[x] = i



XN = len(ts)
st = SegTree([mx]*XN, XN, mx, min)
for t,r,x in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(x2i[x], x if r else mx)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
Query = [list(map(int,input().split())) for _ in range(q)]
x = [0]
for i in range(n):
    if s[i:i+2] == "AC":
        x.append(1)
    else:
        x.append(0)
for l,r in Query:
    tmp = x[l:r]
    print(tmp.count(1))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
Query = [list(map(int,input().split())) for _ in range(q)]
x = [ 0 for _ in range(n) ]
for i in range(n-1):
    if s[i:i+2] == "AC":
        x[i+1] = x[i] + 1
    else:
        x[i+1] = x[i]
for l,r in Query:
    print(x[r-1]-x[l-1])
### BUGGY CODE ###

from collections import Counter
N = int(input())
cnt = Counter(map(int, input().split()))

L = sum([[a] * (c // 2) for a, c in cnt.items()], [])
L.sort()

ans = 0 if len(L) < 2 else L[-1] * L[-2]
print(ans)


### FIXED CODE ###

from collections import Counter

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

cntA = Counter(A)
B = []
for a, c in cntA.items():
    if c // 2 == 0:
        continue
    for _ in range(c // 2):
        B.append(a)

B.sort(reverse=True)
ans = B[0] * B[1] if len(B) >= 2 else 0

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

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

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7

kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

ans=0
x=0
for i in range(N-1):
    x+= (kaijou//(i+1))%(10**9+7)
    ans+= d[i]*x

print(ans%(10**9+7))

### FIXED CODE ###

import math
import sys 
input = sys.stdin.readline

N = int(input())
x = list(map(int,input().split()))
mod = 10**9+7

d = [0]*(N-1)

for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= mod


kaijou = 1
for i in range(1,N):
    kaijou *= i
    kaijou %= mod


ans=0
x=0

def pow_r(x, n):
    """
    O(log n)
    """
    x %= mod
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return (x * (pow_r(x ** 2, (n - 1) // 2)))%mod

for i in range(N-1):
    #(i+1)%(mod-2)を計算してyへ
    y = pow_r(i+1,mod-2)
    #x+= kaijou//(i+1))%(10**9+7)
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

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

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

listx.sort()
listy=[]

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
listy.sort()

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
    else:
        x=listx.pop(0)
        listy.append(x)
    
    if listy[0] > listy[-1]:
        listy.reverse()
ans=0

for i in range(len(listy)-1):
    ans=ans+abs(listy[i]-listy[i+1])

print(ans)





### FIXED CODE ###

import itertools
import numpy as np
data_num = int(input()) 
data = [int(input()) for i in range(data_num)] 
#data_num=5
#data=[6,8,1,2,3]

data.sort()
npdata=np.array(data)

parts1=[1]
parts2=[2 for i in range(data_num-2)]
parts1.extend(parts2)
parts1.append(1)
npparts1=np.array(parts1)

parts0=[(-1)**(i+1) for i in range(data_num)]
npparts0=np.array(parts0)

y=npparts1*npparts0

y=y.tolist()
y.sort()

y=np.array(y)
z1=sum(data*y)

parts01=[(-1)**i for i in range(data_num)]
npparts0=np.array(parts01)

y=npparts1*npparts0

y=y.tolist()
y.sort()
y=np.array(y)
z2=sum(data*y)

print(max(z1,z2))
### BUGGY CODE ###

n = input()
a = [input() for _ in xrange(n)]
ans = max(a)
for i in xrange(n):
  if a[i] != ans:
    print ans
  else:
    print max(a[:i] + a[i + 1:])

### FIXED CODE ###

n = input()
a = [input() for _ in xrange(n)]
ans = max(a)
i = a.index(ans)
ans2 = max(a[:i] + a[i + 1:])
for i in xrange(n):
  if a[i] != ans:
    print ans
  else:
    print ans2
### BUGGY CODE ###

import numpy as np

def count_num_light(a):
  ret = np.array([0 for _ in range(len(a))])
  for i in range(len(a)):
    start = max(0, i-a[i])
    ret[start:i+a[i]+1] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

for i in range(k):
  num_light = count_num_light(a)
  a = num_light.copy()

print(*a)

### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
S = []
As2 = As + As
for i in range(N):
  a = As[i]
  j = As2.index(a, i+1, 2*N)+1
  S.append((j//N, j%N))
#print(S)
count = 0
p = 0
while True:
  c, p = S[p]
  count += c
  if p == 0:
    break
#print(count)
K = K%count
#print(K)
s = []
for k in range(K):
  for a in As:
    i = -1
    for j in range(len(s)):
      if s[j] == a:
        i = j
    if i < 0:
      s.append(a)
    else:
      s = s[0:i]
print(" ".join(map(str, s)))


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))
### BUGGY CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def diff(S, i, T):
    res = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            res += 1
    return res

def solve():
    [N, M] = inlt()
    uf = [i for i in range(N)]
    rn = [1 for i in range(N)]

    def root(i):
        j = i
        while uf[j] != j:
            j = uf[j]
        uf[i] = j
        return j

    def union(i, j):
        if rn[i] > rn[j]:
            i, j = j, i
        ri = root(i)
        rj = root(j)
        if ri == rj:
            return
        uf[ri] = rj
        rn[rj] += rn[ri]

    for i in range(M):
        [a, b] = inlt()
        union(a - 1, b - 1)

    groups = defaultdict(int)
    res = 0
    for i in range(N):
        r = root(i)
        groups[r] += 1
        res = max(res, groups[r])
    
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))


### FIXED CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def dfs(i, edges, visited):
    s = []
    if not visited[i]:
        s.append(i)
        visited[i] = True
    res = 0
    while len(s) > 0:
        v = s.pop()
        res += 1
        for i in edges[v]:
            if not visited[i]:
                s.append(i)
                visited[i] = True

    return res

def solve():
    [N, M] = inlt()
    edges = defaultdict(set)
    visited = [False for i in range(N)]

    for i in range(M):
        [a, b] = inlt()
        edges[a - 1].add(b - 1)
        edges[b - 1].add(a - 1)

    res = 0
    for i in range(N):
        res = max(res, dfs(i, edges, visited))
    
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
ans = 1
for i in a:
    if i == 0:
        ans = 0
    ans *= i
if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ans = 1
for i in a:
    if i == 0:
        ans = 0
        break
    ans *= i
    if ans > 10**18:
        ans = -1
        break

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

N = int(input())
slist = []
for i in range(N):
    slist.append(sorted(list(input())))
count = [0 for i in range(N)]
c = []
c.append(slist[0])
for i in range(N):
    d = 0
    for j in range(len(c)):
        if slist[i] == c[j]:
            count[j] += 1
            d = 1
    if d == 0:
        c.append(slist[i])
count[0] -= 1
def counting(n):
    if n == 0:
        return 0
    else:
        return n*(n+1)//2
sum = 0
for i in range(N):
    sum += counting(count[i])
print(sum)

### FIXED CODE ###

N = int(input())
ssorted = []
for i in range(N):
    ssorted.append("".join(sorted(list(input()))))
sdict = {}
for i in ssorted:
    if i in sdict:
        sdict[i] += 1
    else:
        sdict[i] = 1
count = 0
for i in sdict:
    s = sdict[i]
    if s >= 2:
        count += s*(s-1)//2
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)
if al>0:
    a.sort()

f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=dp[i-1]%mod+dp[i-2]%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
### BUGGY CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

		
def cat_snuke():
	for i in l:
		for j in bone:
			if i == j:
				print("POSSIBLE")
				return 0
	print("IMPOSSIBLE")
	
cat_snuke()

### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

import itertools

n=int(input())
a=list(map(int,input().split()))
l=list(range(1,n+1))
tmpList= (list([x,y] for x,y in (itertools.combinations(l, 2)) if x<y))
ans=0
for item in tmpList:
    if a[item[0]-1]!=item[0] and a[item[1]-1]!=item[1] and a[item[1]-1]==item[0] and a[item[0]-1]==item[1]:
        ans+=1
print (ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a = [None] + a
cnt = 0
for i in range(1, n):
  j = a[i]
  if j > i and a[j] == i:
    cnt += 1
print(cnt)
### BUGGY CODE ###

S=list(input())
ans=0
while 1:
  flag=0
  for i in range(len(S)-1):
    if S[i:i+2]==["0","1"] or S[i:i+2]==["1","0"]:
      del S[i:i+2]
      ans+=2
      flag=1
  
  if flag==0:
    break
print(ans)

### FIXED CODE ###

S=list(input())
sum0=0
for i in range(len(S)):
  if S[i]=="0":
    sum0+=1
 
print(2*min(sum0,len(S)-sum0))
### BUGGY CODE ###

from collections import Counter
import math

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

    cnt = Counter(A)
    # print(cnt)
    def comb(n, r):
        if n - r < 0:
            return 0
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    cnt_comb = {}
    sm = 0
    for key, val in cnt.items():
        tmp = comb(val, 2)
        cnt_comb[key] = tmp
        sm = sm + tmp
    # print(cnt_comb)

    # print(list(A))
    for a in A:
        comb_val = cnt_comb.get(a)
        cmb = comb(cnt.get(a) - 1, 2)
        print(sm - comb_val + cmb)



if __name__ == '__main__':
    solver()


### FIXED CODE ###

from collections import Counter
import math

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

    cnt = Counter(A)
    # print(cnt)
    def comb(n, r):
        if n - r < 0: return 0
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2, r + 1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p - 1, r, p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result
    cnt_comb = {}
    sm = 0
    for key, val in cnt.items():
        tmp = comb(val, 2)
        cnt_comb[key] = tmp
        sm = sm + tmp
    # print(cnt_comb)

    # print(list(A))
    for a in A:
        comb_val = cnt_comb.get(a)
        cmb = comb(cnt.get(a) - 1, 2)
        print(sm - comb_val + cmb)



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

import numpy as np
from itertools import groupby

h,w=map(int,input().split())
M=np.array([list(input()) for i in range(h)])
L=np.array([[0]*w for i in range(h)])

for i in range(w):
	c=0
	for k,g in groupby(M[:,i]):
		l=len(list(g))
		if k=='.':
			L[c:c+l,i]+=l
		c+=l

for i in range(h):
	c=0
	for k,g in groupby(M[i,:]):
		l=len(list(g))
		if k=='.':
			L[i,c:c+l]+=l
		c+=l

print(np.amax(L)-1)


### FIXED CODE ###

h,w=map(int,input().split())
M=[list(input()) for i in range(h)]
D=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
L=[[0]*w for i in range(h)]

for i in range(h):
    c=0
    for j in range(w):
        if M[i][j]=='.':
            c+=1
            R[i][j]=c
        else:
            c=0
for i in range(h):
    c=0
    for j in range(w):
        if M[i][w-1-j]=='.':
            c+=1
            L[i][w-1-j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[i][j]=='.':
            c+=1
            D[i][j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[h-1-i][j]=='.':
            c+=1
            U[h-1-i][j]=c
        else:
            c=0
r=0
for i in range(h):
    for j in range(w):
        r=max(r,R[i][j]+L[i][j]+D[i][j]+U[i][j]-3)
print(r)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [[c]*b for b, c in [map(int, input().split()) for _ in range(M)]]

R=sum(BC,[])
if len(R)>len(A):
    R=sorted(R,reverse=True)[:len(A)]
T=sorted(A+R,reverse=True)
print(sum(T[:len(A)]))



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))
### BUGGY CODE ###

from collections import deque
 
n = int(input())
node_list = []
nodes = [[] for _ in range(n)]
edges = dict()
for _ in range(n - 1):
	a, b = map(int, input().split())
	node_list.append((a - 1, b - 1))
	nodes[a - 1].append(b - 1)
	nodes[b - 1].append(a - 1)
	edges[(a - 1, b - 1)] = 0
 
used_colors = [[] for _ in range(n)]
used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		if edges[(a, b)] == 0:
			for color in range(1, n):
				if not color in used_colors[a] and not used_colors[b]:
					break
			edges[(a, b)] = color
			used_colors[a].append(color)
			used_colors[b].append(color)
		if not used[node]:
			que.append(node)
 
	used[ni] = True
 
print(max(edges.values()))
for node in node_list:
	print(edges[node])

### FIXED CODE ###

from collections import deque

n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	a, b = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
 
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
 
print(max(ans))
for node in node_list:
	print(ans[node])
### BUGGY CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())
edge = np.array([input().split() for _ in range(N-1)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

distance_mat_K = dijkstra(graph, directed = False, indices = K-1)
#print(distance_mat_K)

for i in range(Q):
  print(int(dijkstra(graph, directed = False, indices = XY[i][0]-1)[K-1] + distance_mat_K[XY[i][1]-1]))

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

N = int(input())
lines = readlines()
graph = defaultdict(list)
for line in lines[:N-1]:
  a,b,c = map(int,line.split())
  graph[a].append((b,c))
  graph[b].append((a,c))
Q, K = map(int,lines[N-1].split())
XY = np.array([line.split() for line in lines[N:]],np.int64)

def degreesOfSeparation(graph,start):
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    table = [0] * (len(graph) + 1)
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        #print(frontier,":",degrees)
        #degrees += 1
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next[0] not in visited:
                    visited.add(next[0])
                    newfront.add(next[0])
                    table[next[0]] += next[1] + table[g]
        frontier = newfront
    return table
table = degreesOfSeparation(graph,K)
for q in range(Q):
  print(table[XY[q][0]] + table[XY[q][1]])