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

from bisect import bisect_left
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

pat_sum = 0
for c in C:
  num_b = bisect_left(B, c)
  for b in B[:num_b]:
    num_a = bisect_left(A, b)
    pat_sum += num_a
print(pat_sum)

### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

total = 0
for b in B:
  total += bisect_left(A, b) * (n - bisect_right(C, b))
print(total)
### BUGGY CODE ###

N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
result = [0]*N
numbers = []

for o in operations:
    result[int(o[0])-1] += int(o[1])

for e in edges:
    parent = int(e[0])
    sun = int(e[1])

    if sun in numbers:
        result[parent-1] += result[sun-1]
        numbers.append(parent)
    else:
        result[sun-1] += result[parent-1]
        numbers.append(sun)
        
print(' '.join(map(str, result)))

### FIXED CODE ###

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

tree = [[] for _ in range(N)]
result = [0]*N

for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a-1].append(b)

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

for i in range(N - 1):
    for j in tree[i]:
        result[j-1] += result[i]

print(' '.join(map(str, result)))
### BUGGY CODE ###

import sys

a,aa = map(int,input().split())

b = [10**10 for i in range(a)]

c = list(map(int,input().split()))
b[0] = 0
for i in range(1,a):
	k = min(i,aa)
	for j in range(1,k+1):
		ma = min(b[i],b[i-j] + abs(c[i]-c[i-j]))
		b[i] = ma
print(b[-1])


### FIXED CODE ###

import sys

a,aa = map(int,input().split())

b = [sys.maxsize for i in range(a)]

c = list(map(int,input().split()))
b[0] = 0
for i in range(1,a):
	k = min(i,aa)
	for j in range(1,k+1):
		ma = min(b[i],b[i-j] + abs(c[i]-c[i-j]))
		b[i] = ma
print(b[-1])
### BUGGY CODE ###

#!/usr/bin/env python3

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

def isallodd(arr):
    haseven = False
    for i in arr:
        if i%2==0:
            haseven = True
            break
    if haseven:
        return False
    else:
        return True

ans = 0 
while isallodd(a)==False:
    on = False
    for i in range(len(a)):
        if a[i]%2==1:
            a[i]*=3
        else:
            if on == False:
                a[i]//=2
                on = True
            else:
                a[i]*=3
    ans += 1 

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

def f(n):
    ans = 0 
    while n%2 == 0:
        n //= 2
        ans += 1
    return ans 

ans = 0 
for i in a:
    ans += f(i)

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

import pprint
import networkx as nx
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
graph = nx.DiGraph()
for h, w in itertools.product(range(H), range(W)):
    coord = (h, w)
    edge = (h, w, 'edge')
    if S[h][w] == 'X':
        graph.add_edge('source', edge, capacity=10**10)
    graph.add_edge(coord, edge, capacity=1)
    if 0 < h < H - 1 and 0 < w < W - 1:
        for dh, dw in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            newh, neww = h + dh, w + dw
            newcoord = (newh, neww)
            graph.add_edge(edge, newcoord, capacity=1)
    else:
        graph.add_edge(edge, 'sink', capacity=10**10)
ans = nx.minimum_cut_value(graph, 'source', 'sink')
print(-1 if ans >= 10**10 else ans)


### FIXED CODE ###

import sys
import itertools
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import maximum_flow

H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = lil_matrix((sink + 1, sink + 1), dtype=int)

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph[2 * i, 2 * i + 1] = 1
    else:
        graph[source, 2 * i + 1] = INF
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph[2 * i + 1, 2 * j] = 1
        else:
            graph[2 * i + 1, sink] = INF
graph = graph.tocsr()
ans = maximum_flow(graph, source, sink).flow_value
ans = ans if ans < INF else -1
print(ans)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

def bfs(start, H, W):
    visited = [False for _ in range(H * W)]
    import queue
    q = queue.Queue()
    q.put((start[0], start[1], 0))
    max_dist = 0
    while not q.empty():
        (i, j, dist) = q.get()
        max_dist = max(dist, max_dist)
        visited[i * W + j] = True 
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0 or dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.put((i + dy, j + dx, dist + 1))
    return max_dist

ans = 0
for i in range(H * W):
    start = (i // W, i % W)
    if S[start[0]][start[1]] == '#':
        continue
    ans = max(ans, bfs(start, H, W))
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)
### BUGGY CODE ###

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

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp
#print(x)

p = [1,2]
for val in range(3,x+1):
  flag = 1
  for i in range(2,int(math.sqrt(val))+1):
    if val % i == 0:
      flag = 0
  if flag == 1:
    p.append(val)
out = []
for i in range(len(p)):
  if x%p[i] == 0:
    out.append(p[i])
print(len(out))
  
  

### FIXED CODE ###

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

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
p = []
tmp = int(math.sqrt(x))+1
for n in range(2,tmp):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p.append(1)
p = list(set(p))
print(len(p))
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)


N, M = LI()
LR = []

for i in range(M):
    LR.append(LI())

#低い方と高い方を求める
lower = None
found = False
for i in range(1,N+1):
    if found:
        break
    for lr in LR:
        if not (lr[0] <= i <= lr[1]):
            break
    else:
        lower = i
        found = True

if lower == None:
    print(0)
    exit()
#  print('lower', lower)
if lower == N:
    print(1)
    exit()

upper = None
found = False
for i in reversed(range(lower+1, N+1)):
    if found:
        break
    for lr in LR:
        if not (lr[0] <= i <= lr[1]):
            break
    else:
        upper = i
        found = True
if upper == None:
    upper = lower
#  print('upper', upper)
print(upper - lower + 1)




### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)


N, M = LI()
LR = []

for i in range(M):
    LR.append(LI())

left, right = 0, inf
for lr in LR:
    left = max(left, lr[0])
    right = min(right, lr[1])
#  print(left, right)
if left > right:
    print(0)
else:
    print(right - left + 1)
### BUGGY CODE ###

import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)

    f_original = [False] * (N + 1)
    f = [False] * (N + 1)
    k =0

    pre_revise =set(range(N+1))
    current_revise =set(range(N+1))
    while k<500001: # １日分の作業

        f =[False] * (N + 1)
        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and f[can] is False and f[i] is False:
                L[i].popleft()
                L[can].popleft()
                f[i] = True
                f[can] = True
                current_revise.add(i)
                current_revise.add(can)
        k += 1
        if f == f_original:
            break

    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)


    k =0

    current_revise =set(range(N+1))
    while k<50000000: # １日分の作業

        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and i not in current_revise and can not in current_revise:
                L[i].popleft()
                L[can].popleft()

                current_revise.add(i)
                current_revise.add(can)
        k += 1

        if len(current_revise)==0:
            break


    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

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

d = input()
Q = int(input())
for q in range(Q):
    ls = input().split()
    if ls[0] == '1':
        d = d[::-1]
    else:
        if (ls[1]== '1'):
            
            d = ''.join([ls[2],d])
        else:
            
            d = ''.join([d,ls[2]])
print (d)


### FIXED CODE ###

from collections import deque
d = deque()
s = input()
d.append(s)
rev = 0

Q = int(input())

for q in range(Q):
    ls = input().split()
    #print (ls)
    if ls[0] == '1':
        rev = (rev + 1) % 2
    else:
        if (int(ls[1]) + rev) % 2 == 0:
            d.append(ls[2])
        else:
            d.appendleft(ls[2])

ans = ''.join(list(d))
if rev == 1:
    ans = ans[::-1]
print (ans)
### BUGGY CODE ###

a,b,x = map(int,input().split())
c = range(a,b+1)
ans = 0
for i in range(len(c)):
    if c[i] % x == 0:
        ans +=1
        
print(ans)

### FIXED CODE ###

a,b,x = map(int,input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

import math
 
n,p=map(int,input().split())
 
def C(N,P):
    if N == 1: return P
    
    a=int(P**(1/(N-1)))+1
 
    res=1
    for i in range(2,a):
        if P % i**N == 0 : res = i
 
    return res
 
print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

import math

s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=int(s[1])
for i in range(s[1]):
  for j in range(s[0]):
    if max(t)==t[j] and 0<b:
      t[j]=math.floor(t[j]/2)
      b=b-1
for l in range(s[0]):
  a=a+t[l]
print(a)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
### BUGGY CODE ###

n = int(input())
li = [int(input()) for _ in range(5)]
li.insert(0, 0)
#print(li)
plot = [n, 0, 0, 0, 0, 0]
count = 0
"""for i in range(1, 5):
    print(i)"""
time = 0
while plot[5] != n:
  for i in range(5, 0, -1):
    #print(i)
    if plot[i-1] - li[i] >= 0:
      plot[i-1] -= li[i]
      plot[i] += li[i]
    else:
      plot[i] += plot[i-1]
      plot[i-1] = 0
    #print(plot, time)
    count += 1
  #if count >= 100:
      #break
  time += 1

print(time)


### FIXED CODE ###

N = int(input())
abcde = [int(input()) for _ in range(5)]
mx = min(abcde)
if N % mx == 0:
  ans = 5 + N // mx -1
else:
  ans = 5 + N // mx

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

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    if i%2 == 0:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if n%2 == 0:
    print(" ".join(list(map(str,b))))
else:
    c = []
    for i in range(n-1,-1,-1):
        c.append(b[i])
    print(" ".join(list(map(str,c))))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
9753102468
na = n-1
if na%2 == 0:
    nl = na-1
    nr = na
else:
    nl = na
    nr = na-1

b = []
for i in range(nl,0,-2):
    b.append(i)
for i in range(0,nr+1,2):
    b.append(i)

ans = [0 for i in range(n)]
for i,k in enumerate(b):
    if n%2 == 0:
        ans[i] = a[k]
    else:
        ans[n-1-i] = a[k]
print(" ".join(list(map(str,ans))))
### BUGGY CODE ###

import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    for i in range(k):
        c -= ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)

    print(c % MOD)

    # if k == 1:
    #     # d
    #     c -= 1
    # elif k == 2:
    #     # xd
    #     c -= ncr(L, 1, MOD)
    #     # dx
    #     c -= ncr(N - r, 1, MOD)
    # elif k >= 3:
    #     # xxdxx
    #     for i in range(k):
    #         c -= ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)
    # print(c % MOD)


### FIXED CODE ###

import sys
from collections import Counter

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def mod_invs(max, mod):
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_ncrs(n):
    invs = mod_invs(N + 1, MOD)
    ret = [1]
    ncr = 1
    for i in range(1, n + 1):
        ncr = ((ncr * (n - i + 1) % MOD) * invs[i]) % MOD
        ret.append(ncr)
    return ret


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
side_ncrs = get_ncrs(L + N - r)
while len(side_ncrs) < N + 2:
    side_ncrs.append(0)

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans_ncrs = get_ncrs(N + 1)
while len(ans_ncrs) < N + 2:
    ans_ncrs.append(0)
ans = [(ans_ncrs[k] - side_ncrs[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())

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

for i in range(n):
    B = A[:i] + A[i+1:]
    B = sorted(B)
    print(B[(n)//2-1])

### FIXED CODE ###

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

B = sorted(A)

median_a = B[n//2 - 1]
median_b = B[n//2]
# print(median_a, median_b)

for i in A:
    if i <= median_a:
        print(median_b)
    else:
        print(median_a)
### BUGGY CODE ###

s = str(input())
k = int(input())
s += '0'
result = []
for i in range(1, k+1):
    for j in range(len(s)-i):
        if all(s[j:j+i] != x for x in result):
            result.append(s[j:j+i])
result.sort()
print(result[k-1])

### FIXED CODE ###

def main():
    s = str(input())
    s += '0'
    k = int(input())
    result = set()
    for i in range(1, 6):
        for j in range(len(s)-i):
            result.add(s[j:j+i])
    out = list(result)
    out.sort()
    print(out[k-1])
if __name__ =='__main__':
    main()
### BUGGY CODE ###

s = list(input()[::-1])
mod = 2019
tot = [0]
for i in range(len(s)):
    tot.append((tot[i] + (int(s[i])*(10**i))%mod)%mod)
dp = [0 for _ in range(2020)]
ans = 0
for t in tot:
    ans += dp[t]
    dp[t]+= 1
print(ans)

### FIXED CODE ###

s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)
### BUGGY CODE ###

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

Y = sorted(X)
Y = list(map(lambda x,y:x-y, Y[1:],Y[:-1]))

for i in range(N-1):
	if Y != []:
		x = max(Y)
		Y.remove(x)
	else:
		break

print(sum(Y))


### FIXED CODE ###

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

X.sort()
diffX = list(map(lambda x,y:x-y, X[1:], X[:-1]))
diffX.sort(reverse = True)

if N-1 >= len(diffX):
	print(0)
else:
	print(sum(diffX[N-1:]))
### BUGGY CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append([c,b])
tmp_li.sort(reverse=True)
#print(tmp_li)
count = 0
for t in tmp_li:
    kazu = min(t[1],n-count+1)
    li += [t[0]]*kazu
    if count>=n:
        break
li.sort(reverse=True)
print(sum(li[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n]))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
 
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, M = map(int, input().split())
  p = list(map(int, input().split()))
  xy = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N+1)
  for x, y in xy:
    U.Unite(x, y)
  root_dict = {}
  for i in range(1, N+1):
    root = U.Find_Root(i)
    if root in root_dict:
      root_dict[root] += [i]
    else:
      root_dict[root] = [i]
  ans = 0
  for i in range(1, N+1):
    root = U.Find_Root(i)
    if p[i-1] in root_dict[root]:
      ans += 1
  print(ans)


if __name__ == "__main__":
  main()

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
 
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, M = map(int, input().split())
  p = list(map(int, input().split()))
  xy = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N+1)
  for x, y in xy:
    U.Unite(x, y)
  ans = 0
  for i in range(1, N+1):
    if U.isSameGroup(i, p[i-1]):
      ans += 1
  print(ans)


if __name__ == "__main__":
  main()