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

from collections import deque
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
A = deque(A)
X = []
for _ in range(M):
    b, c = map(int, input().split())
    X.extend([c] * b)
X.sort()
X = deque(X)

for i in range(len(X) if len(X) < len(A) else len(A)):
    a = A.popleft()
    c = X.pop()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print(sum(A))
        quit()
print(sum(A))

### FIXED CODE ###

from sys import stdin
from collections import deque
from operator import itemgetter

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
X = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
X.sort(key=itemgetter(1), reverse=True)
D = []
for b, c in X:
    if len(D) < N:
        D.extend([c] * b)
    else:
        break
D = deque(D)

for i in range(len(D) if len(D) < len(A) else len(A)):
    a = A.popleft()
    c = D.popleft()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print(sum(A))
        quit()
print(sum(A))
### BUGGY CODE ###

x, y = map(int, input().split(' '))
n = min(x, y)

for d in reversed(range(1, n + 1)):
    if (x % d == 0) and (y % d == 0):
        print(d)
        break

### FIXED CODE ###

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x = y
        y = r

    return x

x, y = map(int, input().split(' '))
n = min(x, y)

print(gcd(x, y))
### BUGGY CODE ###


n,m = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(m)]
B = []
C = []
for i in A:
    if 1 in i:
        B += i

for i in A:
    a,b = i
    if a in B:
        C.append(b)
    elif b in B:
        C.append(a)
        


if n in C or n in B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
    

### FIXED CODE ###

n,m = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(m)]
B = []
C = []
for i in A:
    if 1 in i:
        B += i
B = set(B)
for i in A:
    a,b = i
    if a in B:
        C.append(b)
    elif b in B:
        C.append(a)
        
C = set(C)

if n in C or n in B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=list(input().split())
    i=int(query[0])
    if i==1:
        direction=direction^1
    elif i==2:
        f,c=int(query[1]),query[2]
        if f==1 and direction==0:
            s.appendleft(c)
        elif f==1 and direction==1:
            s.append(c)
        elif f==2 and direction==0:
            s.append(c)
        elif f==2 and direction==1:
            s.appendleft(c)

if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        i,f,c=query.split()
        if f=='1' and direction==0:
            s.appendleft(c)
        elif f=='1' and direction==1:
            s.append(c)
        elif f=='2' and direction==0:
            s.append(c)
        elif f=='2' and direction==1:
            s.appendleft(c)


if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))
### BUGGY CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
x = [[0, 0]] * m
for i in range(m):
    b, c = map(int, input().split())
    x[i] = (c, b)
x.sort(reverse=True)
# print("x =", x)
# print("a =", a)
y = []
for i in range(m):
    z = [x[i][0]] * x[i][1]
    y.extend(z)
# print("y =", y)
ans = sum(a)
length = min(n, len(y))
for i in range(length):
    if a[i] >= y[i]:
        break
    ans += y[i] - a[i]
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N, M, P = map(int, input().split())
from collections import deque
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = []
d = deque([0])
visited1 = set()
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if (w,v,u) not in visited1:
            visited1.add((w,v,u))
            edges1.append([w,v,u])
            d.append(u)
edges2 = []
d = deque([N-1])
visited2 = set()
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if (w,u,v) not in visited2:
            visited2.add((w,u,v))
            edges2.append([w,u,v])
            d.append(u)
new_edge = []
for e in edges1:
    if e in edges2:
        new_edge.append(e)
d = [10**10]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for w,v,u in new_edge:
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))

### FIXED CODE ###

N, M, P = map(int, input().split())
from collections import deque,defaultdict
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = set()
d = deque([0])
visited1 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if visited1[w*10**8+v*10**4+u] == False:
            visited1[w*10**8+v*10**4+u] = True
            edges1.add(w*10**8+v*10**4+u)
            d.append(u)
edges2 = set()
d = deque([N-1])
visited2 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if visited2[w*10**8+u*10**4+v] == False:
            visited2[w*10**8+u*10**4+v] = True
            edges2.add(w*10**8+u*10**4+v)
            d.append(u)
new_edge = list(edges1&edges2)
d = [10**10]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for e in new_edge:
        w = e//10**8
        v = e%10**8//10**4
        u = e%10**4
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))
### BUGGY CODE ###

from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    for i in range(3, int(sqrt(n)+1))[0::2]:
        if n % i == 0:
            cash[n] = 0
            return 0
    cash[n] = 1
    return 1

from sys import stdin
cash2 = {}
for i in stdin:
    i = int(i)
    c = sum(isprime(n) for n in range(2, i+1)[1::2]) + 1
    print(c)

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(li.count(i))

### FIXED CODE ###

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

ans = [0] * n
for i in li:
    j = i - 1
    ans[j]  = ans[j] + 1
    
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
array = [i for i in range(1, N+1)]
num = 0

for i in range(1, N):
    num += array[i-1] % array[i]

print(num)

### FIXED CODE ###

N = int(input())
print(N * (N-1) // 2)
### BUGGY CODE ###

def chmax(a, b):
	if a < b:
		return b
	return a

def main():
	N, W = map(int, input().split())
	WV = [list(map(int, input().split())) for _ in range(N)]

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			dp[sumw] = chmax(dp[sumw], dp[sumw - w] + v)
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print(main())


### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

org_list = [R, G, B]
org_list.sort()
first_num = org_list[2]
second_num = org_list[1]
third_num = org_list[0]

count = 0

for i in range(N // first_num + 1):
  if i*first_num > N:
    break
  for j in range(N // second_num + 1):
    if i*first_num + j*second_num > N:
      break
    if (N - i*first_num - j*second_num) % third_num == 0:
      count += 1
 
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

org_list = [R, G, B]
org_list.sort()
first_num = org_list[2]
second_num = org_list[1]
third_num = org_list[0]

count = 0

for i in range(N // first_num + 1):
  for j in range((N-i*first_num) // second_num + 1):
    if (N - i*first_num - j*second_num) % third_num == 0:
      count += 1
 
print(count)
### BUGGY CODE ###

#!venv/bin/python

#N = [ int(x) for x in input().split() ]
#S = input()

N = int(input())
K = []
for n in range(N-1):
    K.append([ int(x) for x in input().split() ])

color = [ None for i in range(N)]
color[0] = 1
solved = 1

next_k = K
while solved < N:
    K = next_k
    next_k = []
    for k in K:
        f = k[0] - 1
        t = k[1] - 1
        l = k[2]
        if color[f]:
            if l % 2 == 0:
                color[t] = color[f]
            else:
                color[t] = color[f] * -1
        elif color[t]:
            if l % 2 == 0:
                color[f] = color[t]
            else:
                color[f] = color[t] * -1
        else:
            next_k.append(k)
            continue
        solved += 1

ans = []
for c in color:
    if c == 1:
        ans.append("1")
    else:
        ans.append("0")
print("\n".join(ans))

### FIXED CODE ###

#!venv/bin/python

#N = [ int(x) for x in input().split() ]
#S = input()

from collections import defaultdict 

N = int(input())
K = []
bridge = defaultdict(list)
for n in range(N-1):
    k = [ int(x) for x in input().split() ]
    K.append(k)
    bridge[k[0]].append([k[1], k[2]])
    bridge[k[1]].append([k[0], k[2]])

color = [ None for i in range(N + 1)]

queue = []
queue.append(1)
color[1] = 1


while queue:
    point = queue.pop()
    for b in bridge[point]:
        if not color[b[0]]:
            queue.append(b[0])
            if b[1] % 2 == 0:
                color[b[0]] = color[point]
            else:
                color[b[0]] = color[point] * -1

ans = []
for c in color[1:]:
    if c == 1:
        ans.append("1")
    else:
        ans.append("0")
print("\n".join(ans))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
import itertools 
combi = itertools.combinations(L, 3)
wa = 0
for c in combi:
    if(c[0] < c[1] + c[2] and c[1] < c[2] +c[0] and c[2] < c[0] + c[1]):
        wa +=1
print(wa)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
wa = 0
import bisect
for i in range(N-1,1,-1):
    for j in range(i-1,0,-1):
        diff = L[i]-L[j]
        k = bisect.bisect_right(L, diff)
        wa += j-k if j-k > 0 else 0           
            
print(wa)
### BUGGY CODE ###

#4問目
s = input()
K = int(input())
result = []
for i in range(1, len(s) + 1):
    if(i == 1):
        for j in list(s):
            result.append(j)
    else:
        n = 0
        m = n + i
        while m <= len(s):
            result.append(s[n:m])
            n += 1
            m = n + i

result = set(result)
s = sorted(result)
print(s[K-1])

### FIXED CODE ###

#4問目
s = input()
K = int(input())
result = []
for i in range(1, min(len(s)+1, 6)):
    if(i == 1):
        for j in list(s):
            result.append(j)
    else:
        n = 0
        m = n + i
        while m <= len(s):
            result.append(s[n:m])
            n += 1
            m = n + i

result = set(result)
s = sorted(result)
print(s[K-1])
### BUGGY CODE ###

from collections import deque
h, w = map(int,input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(a)
    for j in range(w):
        if a[j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or finished[nh][nw]:continue
        finished[nh][nw] = True
        q.append((nh,nw,c[2]+1))
print(c[2])

### FIXED CODE ###

from collections import deque
h, w = map(int,input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(a)
    for j in range(w):
        if a[j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "#" or finished[nh][nw]:continue
        finished[nh][nw] = True
        q.append((nh,nw,c[2]+1))
print(c[2])
### BUGGY CODE ###

def main():
    n,m=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    dp=[[0]*(m+1) for _ in [0]*(n+1)]
    for i in range(n+1):
        dp[i][m]=1
    for i in range(m+1):
        dp[n][i]=1
    for i in range(n-1,-1,-1):
        for j in range(m-1,-1,-1):
            dp[i][j]=(dp[i+1][j]+dp[i][j+1]-(s[i]!=t[j])*dp[i+1][j+1])%(10**9+7)
    print(dp[0][0])
main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    dp=[[0]*(m+1) for _ in [0]*(n+1)]
    for i in range(n+1):
        dp[i][m]=1
    for i in range(m+1):
        dp[n][i]=1
    for i in range(n-1,-1,-1):
        for j in range(m-1,-1,-1):
            dp[i][j]=(dp[i+1][j]+dp[i][j+1]-(s[i]!=t[j])*dp[i+1][j+1])%(10**9+7)
    print(dp[0][0])
main()
### BUGGY CODE ###

n=int(input())
cnt=1;N=n
p=0;q=0;a=1;b=1;c=1
j=1
while j<n:
  N=N-j
  S=[]
  i=1
  while i<N:
    if N%i==0:
      if S.count(i)==0:
        S.append(i)
      if S.count(N//i)==0:
        S.append(N//i)
    i=i+1
  cnt=cnt+len(S)
  #print(j,len(S),S,cnt)
  j=j+1
  N=n
print(cnt)

### FIXED CODE ###

N=int(input())
x=0
for i in range(1,N):
  x=x+(N-1)//i
print(x)
### BUGGY CODE ###

import collections
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  ret=0
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      ret+=1+dfs(u)
  return ret

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
q=collections.deque()
path=[]
checked=[0]*(n+1)
checked[1]=1
q.append((1,[]))
while 1:
  v,p=q.popleft()
  if v==n:
    path=p
    break
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      p.append(u)
      q.append((u,p))
      p=p[:-1]
l=len(path)
if l==1:
  fg=n
  sg=1
else:
  fg=path[l//2]
  sg=path[l//2-1]
checked=[0]*(n+1)
checked[1]=1
checked[fg]=1
ans1=dfs(1)
ans2=(n-2)-ans1
if ans1>ans2:
  print('Fennec')
else:
  print('Snuke')

### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  ret=0
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      ret+=1+dfs(u)
  return ret

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
q=collections.deque()
pn=[-1]*(n+1)
checked=[0]*(n+1)
checked[1]=1
q.append(1)
cnt=0
while cnt!=n-1:
  v=q.popleft()
  for u in g[v]:
    if checked[u]==0:
      cnt+=1
      checked[u]=1
      q.append(u)
      pn[u]=v
path=[n]
while 1:
  tmp=pn[path[-1]]
  if tmp==1:
    break
  path.append(tmp)
path=path[::-1]
l=len(path)
if l==1:
  fg=n
  sg=1
else:
  fg=path[l//2]
  sg=path[l//2-1]
checked=[0]*(n+1)
checked[1]=1
checked[fg]=1
ans1=dfs(1)
ans2=(n-2)-ans1
if ans1>ans2:
  print('Fennec')
else:
  print('Snuke')
### BUGGY CODE ###

from bisect import*
def _add(data,k,x):
    while k<=N:
        data[k]+=x
        k+=k&-k
def add(l,r,x):
    _add(data0,l,-x*(l-1))
    _add(data0,r,x*(r-1))
    _add(data1,l,x)
    _add(data1,r,-x)
def _get(data,k):
    s=0
    while k:
        s+=data[k]
        k-=k&-k
    return s
def query(l,r):
    return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)
N,d,a,*t=map(int,open(0).read().split())
data0=[0]*(N+1)
data1=[0]*(N+1)
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)

### FIXED CODE ###

from bisect import*
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)
N,d,a,*t=map(int,open(0).read().split())
N+=1
z=sorted(zip(*[iter(t)]*2))
data0=[0]*(N+1)
data1=[0]*(N+1)
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)
### BUGGY CODE ###

N = input()
N = int(N)
list_anagram = []
list_modified = []
for n in range(1, N + 1):
    s = input()
    #list_anagram.append(s)
    list_s = []
    for i in range(0, 10):
        list_s.append(s[i])
    list_s.sort()
    s_modified = ''
    for i in range(0, 10):
        s_modified = s_modified + list_s[i]
    list_modified.append(s_modified)
    
m = 0
    
for k in range(0, N):
    for l in range (k + 1, N):
        if list_modified[k] == list_modified[l]:
            m += 1
        else:
            continue
print(m)

### FIXED CODE ###

N = int(input())
list_anagram = [''.join(sorted(str(input()))) for i in range(N)]
 
list_anagram.sort()
ans = 0
 
x = 1
 
for i in range(1, N):
    if i != N - 1 and list_anagram[i] == list_anagram[i - 1]:
        x += 1
    elif i != N - 1 and list_anagram[i] != list_anagram[i - 1]:
        ans = ans + x * (x - 1) // 2
        x = 1
    elif i == N - 1 and list_anagram[i] == list_anagram[i - 1]:
        x += 1
        ans = ans + x * (x - 1) //2
    else:
        ans = ans + x * (x - 1) // 2
 
print(ans)
### BUGGY CODE ###


import collections

def main():
  n = int(input())
  A = tuple(sorted(map(int, input().split())))
  D = collections.defaultdict(int)
  for a in A:
    D[a] += 1

  ans = n
  for i in range(n):
    a = A[i]
    if D[a] > 1:
      ans -= 1
      continue

    for b in A[:i]:
      if a % b == 0:
        ans -= 1
        break

  print(ans)


main()


### FIXED CODE ###


import collections

def main():
    n = int(input())
    A = sorted(map(int, input().split()))

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()
### BUGGY CODE ###

from itertools import combinations
N = int(input())
L = list(map(int,input().split()))
lis = combinations(L,3)
ans = 0
for thr in lis:
    if thr[0]<thr[1]+thr[2] and thr[1]<thr[2]+thr[0] and thr[2]<thr[0]+thr[1]:
        ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1
        nc = bisect_left(L,a+b)
        ans += nc-nb-1
print(ans)
### BUGGY CODE ###

from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


for y in range(h):
    for x in range(w):
        if s[y][x]=='.':
            s[y][x]=10000000


s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]
while que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]!="#":
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = 0
A.sort()
B.sort()
C.sort()
for i in range(N, 0, -1):
    for j in range(N, 0, -1):
        #print(B[j-1],C[i-1],"BC")
        if B[j-1] < C[i-1]:
            for k in range(N, 0, -1):
                #print(A[k-1],B[j-1],"AB")
                if A[k-1] < B[j-1]:
                    ans = ans + k
                    break
else:
    print(ans)

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0

A.insert(0,-1)
A.append(10e+10)
C.insert(0,-1)
C.append(10e+10)

for bi in B:
    left = 0
    right = n+1
    
    while right-left>1:
        middle = (left+right) //2
        if A[middle]>=bi:
            right = middle
        else:
            left = middle
    a_count = left

    left = 0
    right = n+1
    while right-left>1:
        middle = (left+right) //2
        if C[middle]>bi:
            right = middle
        else:
            left = middle
    c_count = n+1-right

    count += a_count*c_count

print(count)