Harryxun/stf_run huggingface dataset:
import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
for i in range(M):
  t.append(A.count(C[i]))
  temp = A.count(C[i])
  anst += math.factorial(temp)/(math.factorial(temp-2)*2)

#print(t)
#print(anst)
#print(jisyo[1])
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-t[C.index(A[i])]+1))

### FIXED CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
n,m = map(int,input().split())
s = [list(map(int,input().split()))[1:]for i in range(m)]
p = list(map(int,input().split()))
form = "0"+str(n)+"b"
ans = 0
for i in range(2**n):
    ptn = format(i,form)
    light = True
    for j in range(m):
        s = sum(int(ptn[k-1])for k in s[j])
        if s%2 != p[j]:
            light = False
    if light == True:
        ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:]for i in range(m)]
p = list(map(int,input().split()))
form = "0"+str(n)+"b"
ans = 0
for i in range(2**n):
    ptn = format(i,form)
    light = True
    for j in range(m):
        s = sum(int(ptn[k-1])for k in l[j])
        if s%2 != p[j]:
            light = False
    if light == True:
        ans += 1
print(ans)
N = int(input())
root = int(N**0.5)
for i in range(root,1,-1):
  if N % i ==0:
    break

print(N/i + i -2)


### FIXED CODE ###

N = int(input())
root = int(N**0.5)
for i in range(root,-1,-1):
  if N % i ==0:
    break

print(int(N/i + i -2))
from math import sqrt
import sys
sys.setrecursionlimit(10**6)
def f(b, n):
	if n < b:
		return n
	else:
		return f(b, n // b) + n % b

n = int(input())
s = int(input())

if n < s:
	print(-1)
divs = []
for i in range(1, int(sqrt(n-s))+1):
	if (n-s)%i == 0:
		if i>2:
			divs.append(i)
		if i != (n-s)//i:
			divs.append((n-s)//i)
divs.sort()
for d in divs:
	if f(d+1, n) == s:
		print(d+1)
		break
else:
	print(-1)

### FIXED CODE ###

from math import sqrt
import sys
sys.setrecursionlimit(10**6)
def f(b, n):
	if n < b:
		return n
	else:
		return f(b, n // b) + n % b

n = int(input())
s = int(input())

if n < s:
	print(-1)
elif n == s:
	print(n+1)
else:
	divs = []
	for i in range(1, int(sqrt(n-s))+1):
		if (n-s)%i == 0:
			divs.append(i)
			if i != (n-s)//i:
				divs.append((n-s)//i)
	divs.sort()
	for d in divs:
		if f(d+1, n) == s:
			print(d+1)
			break
	else:
		print(-1)
n = str(input())
d = []
p = []
i = 1
s = 1
l = 1
for k in n:
 if i % 2 == 0:
  if k == "R" or k == "U" or k == "D":
   #print(k,"は満たしています")
  else:
   #print("偶数","みたしていない")
   s = 0
 else:
  if k == "L" or k == "U" or k == "D":
   #print("奇数","番目の",k)
  else:
    #print("奇数","みたしていない")
    l = 0
 i = i + 1
if s or l == "1":
 print("Yes")
else:
 print("No")

### FIXED CODE ###

n = str(input())
d = []
p = []
i = 1
s = 1
l = 1
for k in n:
 if i % 2 == 0:
  if k == "L" or k == "U" or k == "D":
   pass
  else:
   s = 0
 else:
  if k == "R" or k == "U" or k == "D":
   pass
  else:
    l = 0
 i = i + 1
#print(s,l)
if s and l == 1:
 print("Yes")
else:
 print("No")
import sys
sys.setrecursionlimit(10**12)

N, M = map(int, input().split())
link = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    link[a-1].append([b-1, c])
visited = [0] * N
ans = 0

#全ての頂点からループしてないか確かめるといけないかな？
def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
a = [0] * M
b = [0] * M
c = [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    c[i] = -c[i]
    
INF = 10 ** 13
dist = [INF] * N

dist[0] = 0

for loop in range(N-1):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]

ans = dist[N-1]

nega = [0] * N

for loop in range(N):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]
            nega[b[i]-1] = 1
        if nega[a[i]-1] == 1:
            nega[b[i]-1] = 1

if nega[N-1]:
    print('inf')
else:
    print(-ans)
t=list(input())
for i in range(len(t)):
    if t[i]=="?":
        t[i]=D
    print(t[i],end="")

### FIXED CODE ###

t=list(input())
for i in range(len(t)):
    if t[i]=="?":
        t[i]="D"
    print(t[i],end='')
#print("Hello World!")
A,B,C=map(int,raw_input().split() )
#print("end")
if A+B>=C:
    print("Yes\n")
else:
    print("No\n")


### FIXED CODE ###

A,B,C=map(int,input().split() )
if A+B>=C:
    print("Yes\n")
else:
    print("No\n")
A=input()
B=input()
C=input()
D=[]
E=[]
F=[]
s=a
x=len(A)
y=len(B)
z=len(C)
for i in range(len(A)):
    D.append(A[i])
for i in range(len(B)):
    E.append(B[i]) 
for i in range(len(C)):
    F.append(C[i])
while x>=0 and y>=0 and z>=0:
    if s==a:
        if x==0:
            print("A")
            break
        else:
            count=D[0]
            D.pop(0)
            x-=1
    elif s==b:
        if y==0:
            print("B")
            break
        else:
            count=E[0]
            E.pop(0)
            y-=1
    elif s==c:
        if z==0:
            print("C")
            break
        else:
            count=F[0]
            F.pop(0)
            z-=1
 

### FIXED CODE ###

sa = input()
sb = input()
sc = input()
turn = sa[0]
sa = sa[1:]
while True:
    if turn == 'a':
        if not sa:
            win = 'A'
            break
        else:
            turn = sa[0]
            sa = sa[1:]
    if turn == 'b':
        if not sb:
            win = 'B'
            break
        else:
            turn = sb[0]
            sb = sb[1:]
    if turn == 'c':
        if not sc:
            win = 'C'
            break
        else:
            turn = sc[0]
            sc = sc[1:]
print(win)
A<B=map(int,input().split())

if A+B>9:
  print('error')
else:
  print(A+B)

### FIXED CODE ###

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

if A+B>9:
  print('error')
else:
  print(A+B)
import math

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

A.sort()
A.reverse()

t=A[0]
for i in range(1,N):
    t=math.gcd(t,A[i])

if K > A[0]:
    print("IMPOSSIBLE")
else:
    if K%t==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    

### FIXED CODE ###

import math

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

A.sort()
A.reverse()

t=A[0]

def myGCD(a,b):
    while b!=0:
        a,b=b,a%b 
    return(a)   

for i in range(1,N):
    t=myGCD(t,A[i])

if K > A[0]:
    print("IMPOSSIBLE")
else:
    if K%t==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    A=LI()
    B=[0]*N
    C=[0]*N
    for i in range(M):
        B[i],C[i]=MI()
    
    C,B=zip(*sorted(zip(C,B)))
    B=B[::-1]
    C=C[::-1]
    
    import heapq
    heapq.heapify(A)
    
    for i in range(M):
        b=B[i]
        c=C[i]
        for _ in range(b):
            a=heapq.heappop(A)
            if a>=c:
                heapq.heappush(A,a)
                break
            else:
                heapq.heappush(A,c)
                
    ans=0
    for i in range(N):
        a=heapq.heappop(A)
        ans+=a
        
    print(ans)

main()


### FIXED CODE ###

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

for i in range(M):
    CB[i][1],CB[i][0]=map(int,input().split())
    
A.sort()
CB.sort(reverse=True)

#Aを小さい順に見る，Cが大きい順に変更操作をして確定していく
cc=0
ans=0
for i in range(N):
    if cc<M:
        if A[i]<CB[cc][0]:
            A[i]=CB[cc][0]
            CB[cc][1]-=1
            if CB[cc][1]==0:
                cc+=1
    ans+=A[i]
        
print(ans)
n = int(input())
a = list(map(int, input().split()))
for i in range(1,n+1):
    if i in a:
        print(a.count(i))
    else:
        print(0)

### FIXED CODE ###

import math
r = int(input())
x = math.pi
print(r*2*x)
import math

a,b,c,d = map(int,input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

gcd_cd = lcm(c,d)

a_c_numbers = a//c
if a % c == 0:
    a_c_numbers -= 1
a_d_numbers = a//d
if a % d == 0:
    a_d_numbers -= 1

a_numbers = a_c_numbers + a_d_numbers

b_c_numbers = b//c
b_d_numbers = b//d
b_numbers = b_c_numbers + b_d_numbers

gcd_cd_numbers = b//gcd_cd - a//gcd_cd

# print(a_c_numbers,a_d_numbers)
# print(b_c_numbers,b_d_numbers)
# print(gcd_cd_numbers)
# print(b_numbers - a_numbers - gcd_cd_numbers)
print(b - a + 1 - (b_numbers - a_numbers - gcd_cd_numbers))

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

gcd_cd = lcm(c,d)

a_c_numbers = a//c
if a % c == 0:
    a_c_numbers -= 1
a_d_numbers = a//d
if a % d == 0:
    a_d_numbers -= 1

a_numbers = a_c_numbers + a_d_numbers

b_c_numbers = b//c
b_d_numbers = b//d
b_numbers = b_c_numbers + b_d_numbers

if a % gcd_cd == 0:
    gcd_cd_numbers = b//gcd_cd - a//gcd_cd + 1
else:
    gcd_cd_numbers = b//gcd_cd - a//gcd_cd

# print(a_c_numbers,a_d_numbers)
# print(b_c_numbers,b_d_numbers)
# print(gcd_cd_numbers)
# print(b_numbers - a_numbers - gcd_cd_numbers)
ans = b - a + 1 - (b_numbers - a_numbers - gcd_cd_numbers)

if ans > 0:
    print(ans)
else:
    print(0)
# C
from functools import reduce
import math

def lcm(a, b):
    return int(a*b/math.gcd(a, b))

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

result = 0
mod = reduce(lcm, a)-1

for i in range(len(a)):
    result += mod % a[i] 

print(int(result))

### FIXED CODE ###

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

print(sum(a) - n)
s = int(input())
for i in range(-s, s):
    for j in range(-s, s):
    if i**5-j**5 == s:
        if i > j:
            print(i, j) 
            break

### FIXED CODE ###

x=int(input())
for i in range(-200,200):
  for j in range(-200,200):
    if (i**5)-(j**5)==x:
      print(i,j)
      exit()
b = [int(x) for x in input().split()]
 
if (b < a):
    tmp = b
    b = a
    a = tmp
 
 
x = 1
while True:
    if (int(x*0.08) == a and int(x*0.1) == b):
        print(x)
        break
    else:
        if (x > 1500):
            print(-1)
            break
        else:
            x += 1

### FIXED CODE ###

a, b = [int(x) for x in input().split()]
 
if (b < a):
    tmp = b
    b = a
    a = tmp
 
 
x = 1
while True:
    if (int(x*0.08) == a and int(x*0.1) == b):
        print(x)
        break
    else:
        if (x > 1500):
            print(-1)
            break
        else:
            x += 1
S=list(input())
N=int(input())
P=list()
jia= N%26
for i in range(len(S)):
  xin= ord(S[i])+jia
  if xin > ord("Z"):
   xin-=26
  zimu=chr(xin)
  P+=zimu
p=''.join(P)
print(p)


### FIXED CODE ###

N=int(input())
S=list(input())
P=list()
jia= N%26
for i in range(len(S)):
  xin= ord(S[i])+jia
  if xin > ord("Z"):
   xin-=26
  zimu=chr(xin)
  P+=zimu
p=''.join(P)
print(p)
import numpy as np
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"
print(np.array(another_box))
def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

if flag==1:print(count)
else:print(-1)

### FIXED CODE ###

h,w=map(int,input().split())
b=[["#"]*(w+2)]
a=0
for i in range(h):
  c=["#"]
  for j in input():
    a+=j=="#"
    c.append(j)
  b.append(c+["#"])
b+=[["#"]*(w+2)]
b[h][w]=0
Q=[(1,1)]
x=0
y=-1
while Q:
	x+=1
	p=[]
	for i,j in Q:
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if b[i+dx][j+dy]==".":
				p+=[(i+dx,j+dy)]
				b[i+dx][j+dy]="#"
			elif b[i+dx][j+dy]==0:
				y=x
	if y>0:break
	Q=p
if y>0:print((h*w)-a-y-1)
else:print(-1)
N = int(input())
X = list(map(int,input().split()))
ans = []

for i in range(min(X),max(X)+1):
    ans.append(cnt)
    cnt = 0
    for j in X:
        cnt += (j-i)**2
    #ans.append(cnt)
        
print(min(ans))            
        

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
ans = []

for i in range(min(X),max(X)+1):
    cnt = 0
    for j in X:
        cnt += (j-i)**2
    ans.append(cnt)
        
print(min(ans))
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = len(A)//2
    while(True):
        if(right - left < 2):
            if(x[0]<A[left][0]):A.insert(left,x)
            else :
                if(x[0]<A[right[0]]):A.insert(right,x)
                else:A.insert(right+1,x)
            break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left)//2

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
r = float(input())

s = r * r * math.pi
l = r * 2 * math.pi

print("{0:.5f}{1:.5f}"format(s, l))

### FIXED CODE ###

import math
r = float(input())
 
s = r * r * math.pi
l = r * 2 * math.pi
 
print("{0:.5f} {1:.5f}".format(s, l))
from collections import defaultdict
s = str(input())
d = defaultdict(int)
for x in s:
  d[x]+=1
if len(d)==2:
  for key,value in d:
    if value!=2:
      print("No")
      exit()
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

from collections import defaultdict
s = str(input())
d = defaultdict(int)
for x in s:
  d[x]+=1
if len(d)==2:
  for key in d:
    if d[key]!=2:
      print("No")
      exit()
  print("Yes")
else:
  print("No")
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,k = map(int,input().split())
mod = 10**9 + 7
for i in range(1,k+1):
    if k-i== 0:
        print(combinations_count(n-k+1,i)% mod)
    else:
        print((combinations_count(n-k+1,i)*combinations_count(k-i+1,i-1) ) % mod)

### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,k = map(int,input().split())
mod = 10**9 + 7
for i in range(1,k+1):
    if n-k+1 < i:
        print(0)
    elif k-i== 0:
        print(combinations_count(n-k+1,i)% mod)
    else:
        a = math.factorial(k-1)//(math.factorial(k-i)*math.factorial(i-1))
        print((combinations_count(n-k+1,i)*a) % mod)
s_list = list(s)

print(min(s_list.count('1'), s_list.count('0')) * 2)

### FIXED CODE ###

s = input()
s_list = list(s)

print(min(s_list.count('1'), s_list.count('0')) * 2)
n,m = map(int, input().split())

ma = m//n
re = m%n

flag=0

if re==0:
    while(flag==0):
        if m%ma==0:
            print(ma)
            flag = 1
        ma -=1
else:
    flag2=0
    while(flag==0):
        if m%ma==0:
            print(ma)
            flag = 1
            
        if flag2==0:
            ma -=1
            if ma%re==0:
                flag2=1
        
        else:
            ma -= re

### FIXED CODE ###

n,m = map(int, input().split())
 
ma = m//n
 
flag=0
 
while(flag==0):
    if m%ma==0:
        print(ma)
        flag = 1
    ma -=1
a, b = map(int, input().split())
cnt = 0
soc = 1
while soc < b:
    soc += a - 1
    cnt += 1
print(cnt)

### FIXED CODE ###

s = input()
t = input()
cnt = 0
for i in range(3):
    if s[i] == t[i]:
        cnt += 1
print(cnt)
L,R = map(int, input().split())
if L * R < 2019:
        print(L * R)
        exit()

if R - L >= 2019:
        print(0)
        exit()

li=range(L, R)
tmp = []
for i in range(min(2019, R - L)):
        if li[i] % 2019 == 0:
                print(0)
                exit()
        tmp.append(li[i] % 2019)
tmp.sort()

print(tmp[0]* tmp[1])



### FIXED CODE ###

import itertools
L,R = map(int, input().split())
if (R - L) + 1 >= 2019:
        print(0)
        exit()
elif (R - L) + 1 >= 673:
        print(0)
        exit()

if (R - 1) * R < 2019:
        print(L * R)
        exit()


if L % 2019 == 0:
        print(0)
        exit()
elif L % 673 < R % 673:
        li = range(L, R + 1)
        cmb = list(itertools.combinations(li,2))
        ans = (R-1) * R
        for i,j in cmb:
                ans = min(ans, (i*j) % 2019)
        print(ans)

else:
        print(0)
        exit()
s = input()
k = int(input())
for i in range(len(s)):
    if s[i] != "1":
        ans = int(s[i])
        break
print(ans)

### FIXED CODE ###

s = input()
k = int(input())
ans = 1
if k <= len(s):
    if s[:k] == "1" * k:
        ans = 1
    else:
        for i in range(len(s)):
            if s[i] != "1":
                ans = int(s[i])
                break
else:
    for i in range(len(s)):
        if s[i] != "1":
            ans = int(s[i])
            break
print(ans)
from collections import Counter
inp = list(map(int,input().split()))
c=Counter(inp)
inp=[]
for item in c.keys():
  if c[item]==1:
    inp.append(item)
arr=[1]*len(inp)
inp.sort()
ans=0
for i in range(len(inp)):
  if arr[i]==0:
    continue
  else:
    ans+=1
   	for j in range(i+1,len(inp)):
      if inp[j]%inp[i]==0:
        arr[j]=0
print (ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*(max(inp)+1)
inp.sort()
d=Counter([])
for i in range(len(arr)):
    if c[i]>=1 and arr[i]==1:
        if d[i]==0:
            d[i]+=1
        else:
            continue
        k=2
        while k*i<len(arr):
            arr[k*i]=0
            k+=1
ans=0
for item in d.keys():
    if c[item]==1:
        ans+=1
print (ans)
print(x**3)

### FIXED CODE ###

x = raw_input()
x = int(x)
print x*x*x
n = int(input())
a = list(int(i) for i in input().split())
sa = [0] * (n+1)
num_cnt = {}    
# 累積和
for i in range(n):
    sa[i + 1] = sa[i] + a[i]

for num in sa:
    if num in num_cnt:
        num_cnt[num] += 1
    else:
        num_cnt[num] = 1

for cnt in num_cnt.values():
    res += cnt*(cnt-1)//2

print(res)


### FIXED CODE ###


n = int(input())
a = list(int(i) for i in input().split())
sa = [0] * (n+1)
num_cnt = {}    
# 累積和
for i in range(n):
    sa[i + 1] = sa[i] + a[i]

for num in sa:
    if num in num_cnt:
        num_cnt[num] += 1
    else:
        num_cnt[num] = 1


res = 0
for cnt in num_cnt.values():
    res += cnt*(cnt-1)//2

print(res)
S = int(input())

A = [0,0,1]
if S == 1 or S == 2:
  print(0)
elif S == 3:
  print(1)
else:
  for i in range(3,S):
    A += [A[i-1] + A[i-3]]
print(A[i] % (10 ** 9 + 7))

### FIXED CODE ###

S = int(input())
 
A = [0,0,1]
if S == 1 or S == 2:
  print(0)
elif S == 3:
  print(1)
else:
  for i in range(3,S):
    A += [A[i-1] + A[i-3]]
  print(A[i] % (10 ** 9 + 7))
N, Q = map(int, input().split())
rl = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rl[a].append(b)
    rl[b].append(a)
cnt = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x

def dfs(v, pv):
    for next_v in rl[v]:
        if next_v == pv:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)
dfs(0, -1)
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

count = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x

stack = [0]
visited = [0] * N
while stack:
    v = stack.pop()
    visited[v] = 1
    for next_v in to[v]:
        if visited[next_v] == 1:
            continue
        count[next_v] += count[v]
        stack.append(next_v)
print(*count)
N = int(input())

if N == 1:
    print(0)
    exit()

ans = []
end = int(N ** (1/2))
for i in range(2, end + 1):
    while N % i == 0:
        ans.append(i)
        N = N // i

if len(ans) == 0:
    print(1)
    exit()

count = 0
trans = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

res = 0
for i in range(len(ans) - 1):
    if ans[i] != ans[i+1]:
        for j in range(len(trans)):
            if count > trans[j]:
                continue
            else:
                res += (j + 1)
                break
        count = 1
    else:
        count += 1

if ans[-1] == ans[-2]:
    if ans[-1] == ans[0]:
        count += 1
    for j in range(len(trans)):
        if count > trans[j]:
            continue
        elif count == trans[j]:
            res += (j + 1)
            break
        else:
            res += (j)
            break
else:
    res += 1

print(res)

### FIXED CODE ###

N = int(input())


hash = {}
end = int(N ** (1/2))
for i in range(2, end + 1):
    while N % i == 0:
        if i in hash:
            hash[i] += 1
        else:
            hash[i] = 1
        N = N // i
if N != 1:
        if N in hash:
            hash[N] += 1
        else:
            hash[N] = 1

if len(hash.keys()) == 0 and N != 1:
    print(1)
    exit()


count = 0
trans = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

res = 0
for i in hash.values():
    for j in range(len(trans)):
        if i > trans[j]:
            continue
        elif i == trans[j]:
            res += (j + 1)
            break
        else:
            res += j
            break



print(res)
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
min_val = sorted(A)[0]
for _ in range(M):
  B, C = map(int, input().split())
  if min_val <= C:
  	A.extend([C]*B)
    A = sorted(A)[:N]
    min_val = A[0]
  
A = sorted(A, reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC = sorted(BC, key=lambda x: x[1], reverse=True)
# print("A: {}".format(A))
# print("BC: {}".format(BC))

A_dash = []
for ij in BC:
    i, j = ij
    A_dash.extend([j]*i)
    if len(A_dash) >= N:
        break
A_dash = A_dash[:N]

A_dash.extend(A)
A_dash = sorted(A_dash, reverse=True)[:N]

print(sum(A_dash))