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

import sys
import bisect
input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
A.sort()
#print(A)
for b,c in zip(B,C):
    index = bisect.bisect_left(A,c)
    #print(index)
    if index != 0:
        for _ in range(b):
            bisect.insort_left(A,c)
        del A[:b]
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
import bisect
import numpy as np
#input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(B),np.array(C)))
matrix = matrix[:, np.argsort(-matrix[1])]
list2=np.zeros(N)
i=0
for b,c in zip(matrix[0],matrix[1]):
    i += b
    #print(i-b,b)
    if i < N:
        list2[i-b:i] = c
        #print(list2)
    else: 
        list2[i-b:]=c
        #print(list2)
A.extend(list(list2))
A.sort()
print(int(sum(A[N:])))
### BUGGY CODE ###

S = input()
# 0 のとき赤色、1 のとき青色
stack=[]
for s in S:
    stack.append(s)
# print(stack)
cnt=0 #消せた数
while "1" in stack and "0" in stack:
    for i in range(len(stack)-1):
        # print(stack)
        # print(i)
        if stack[i] != stack[i+1]:
            if len(stack) >= 2:
                stack.pop(i)
                stack.pop(i)
                cnt += 2
                break
            # else:
            #     stack.pop(i)
            #     cnt += 2
            #     break
print(cnt)


### FIXED CODE ###

S = input()
# 0 のとき赤色、1 のとき青色
stackA=[]
stackB=[]
for s in S:
    if s == "0":
        stackA.append(s)
    else:
        stackB.append(s)
print(min(len(stackA),len(stackB))*2)
### BUGGY CODE ###

def exp(n):
  return sum(range(n + 1)) / n

N, K = map(int, input().split())
p = list(map(int, input().split()))
a = [0.0]
for i in range(N):
  a.append(a[i] + exp(p[i]))
m = 0
for i in range(N - K + 1):
  m = max(m, a[i + K] - a[i])
print(m)

### FIXED CODE ###

def exp(n):
  return n * (n + 1) / n / 2

N, K = map(int, input().split())
p = list(map(int, input().split()))
a = [0.0]
for i in range(N):
  a.append(a[i] + exp(p[i]))
m = 0
for i in range(N - K + 1):
  m = max(m, a[i + K] - a[i])
print(m)
### BUGGY CODE ###

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

for i in range(n):
	b=a.pop(0)
	print(max(a))
	a.append(b)


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a,reverse=True)
for i in range(n):
	if b[0]!=a[i]:
		print(b[0])
	else:
		print(b[1])
### BUGGY CODE ###

K = int(input())

def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a%b)

def gcd3(a,b,c):
  return gcd(a, gcd(b,c))

ans = 0

for x in range(1,K+1):
  for y in range(1,K+1):
    for z in range(1,K+1):
      ans += gcd3(x,y,z)

print(ans)

### FIXED CODE ###

K = int(input())

def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a%b)

def gcd3(a,b,c):
  return gcd(a, gcd(b,c))

ans = 0

for x in range(1,K+1):
  for y in range(1,K+1):
    for z in range(1,K+1):
      ans += gcd3(x,y,z)

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


import numpy as np
def is_even(num):
  if num % 2 == 0:
    return True
  else:
    return False
  
N=int(input())
ps=[]
for i in range(N):
  tmp=input()
  ps.append([int(tmp.split()[0]),int(tmp.split()[1])])
    

tg=[]
tp=[]

ag=[]
ap=[]
for p in ps:
  tg.append((p[1]+p[0]))
  tp.append(p[0])
  ag.append((p[0]+p[1]))
  ap.append(p[1])
    
    
    
    
T=0
A=0

for i in range(N):
  if is_even(i):
    if tg[np.argmax(tg)]!=0:
      tmpIndex=np.argmax(tg)
      T+=tp.pop(tmpIndex)
      tg.pop(tmpIndex)
      ag.pop(tmpIndex)
      ap.pop(tmpIndex)
    else:
      tmpIndex=np.argmax(tp)
      T+=tp.pop(tmpIndex)
      tg.pop(tmpIndex)
      ag.pop(tmpIndex)
      ap.pop(tmpIndex)
  else:
    if ag[np.argmax(ag)]!=0:
      tmpIndex=np.argmax(ag)
      A+=ap.pop(tmpIndex)
      ag.pop(tmpIndex)
      tg.pop(tmpIndex)
      tp.pop(tmpIndex)
    else:
      tmpIndex=np.argmax(ap)
      A+=ap.pop(tmpIndex)
      ag.pop(tmpIndex)
      tg.pop(tmpIndex)
      tp.pop(tmpIndex)
print(T-A)


### FIXED CODE ###

N=int(input())
ps=[]
tp=[]
ap=[]
for i in range(N):
  p=input().split()
  ps.append([int(p[0])+int(p[1]),i])
  tp.append(int(p[0]))
  ap.append(int(p[1]))
    
def is_even(num):
  if num % 2 == 0:
    return True
  else:
    return False

T=0
A=0
calc=sorted(ps,reverse=True)
#print(calc)
i=0
for p,j in calc:
  if is_even(i):
    T+=tp[j]
  else:
    A+=ap[j]
  i+=1
print(T-A)
### BUGGY CODE ###

import math

n, m = map(int, input().split(' '))

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

for i in range(m):
    idx = a.index(max(a))
    a[idx] = a[idx] / 2

b = sum([math.floor(i) for i in a])
print(b)

### FIXED CODE ###

import math
from heapq import heappush, heappop

n, m = map(int, input().split(' '))

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

h = []

for i in a:
    heappush(h, -i)

for i in range(m):
    v = heappop(h)
    heappush(h, -(-v // 2))

print(-sum(h))
### BUGGY CODE ###

import sys
input_first = input()
N= int(input_first)

wordl = []
timesl = []

for i in range(N):
    S = input()
    if S in wordl:
        timesl[wordl.index(S)] +=1
    else:
        wordl.append(S)
        timesl.append(1)

maxval =max(timesl) 
maxind = [j for j,val in enumerate(timesl) if val == maxval]

resultl=[]
for i in maxind:
    resultl.append(wordl[i])

resultl.sort()

for i in resultl:
    print(i)

### FIXED CODE ###

import sys
input_first = input()
N= int(input_first)

worddic={}

for i in range(N):
    S = input()
    if S in worddic:
        worddic[S] +=1
    else:
        worddic[S] =1

# result=[keyval[0] for keyval in worddic.items() if keyval[1]==max(worddic.values())]

maxval = 0
for i in worddic.items():
    if i[1] > maxval :
        maxval = i[1]
        result=[]
        result.append(i[0])
    elif i[1] == maxval:
        result.append(i[0])
    else:
        pass

result.sort()
for i in result:
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3

def cmb(n,r):
    ans = 1
    for i in range(r):
      ans *= n-i
    for i in range(1,r+1):
      ans //= i
    return ans
n,a,b = map(int,input().split())
mod = 10**9 + 7
def exp_2(n):
  if n == 0: return 1
  if n % 2: return 2 * exp_2(n//2)**2
  else: return exp_2(n//2)**2
print((exp_2(n) - 1 - cmb(n,a) - cmb(n,b))%mod)


### FIXED CODE ###

#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)
### BUGGY CODE ###

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
MOD = 10**9+7

for i in range(len(As)-1):
    tmp = As[i] * sum(As[i+1:])
    tmp %= MOD
    result = (result+tmp) % MOD

print(result)



### FIXED CODE ###

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
MOD = 10**9+7

S = sum(As)

for i in range(len(As)-1):
    S -= As[i]
    tmp = As[i] * S
    result += tmp
    result %= MOD

print(result)
### BUGGY CODE ###

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

MOD = 1000000007
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        ans += (a[i] % MOD) * (a[j] % MOD)
        ans = ans % MOD

print(ans)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

MOD = 1000000007
ans = 0

k = 0
s = [0] * n
for i in range(n-1, 0, -1):
    k += a[i] % MOD
    s[i] = k

for i in range(n-1):
    ans += a[i] * s[i+1]

ans = ans % MOD

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

n, k = map(int, input().split())
H = list(map(int, input().split()))

dp = [10 ** 12] * (n)
dp[0] = 0
dp[1] = abs(H[1] - H[0])

for i in range(1, n-1):
  dp[i+1] = min([dp[i-j] + abs(H[i+1] - H[i-j]) for j in range(min(k, i+1))])
  
ans = dp[n-1]

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
dp[1] = abs(h[0] - h[1])
for i in range(1, n):
  dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, k + 1) if i - j >= 0)
print(dp[-1])
### BUGGY CODE ###

n=int(input())

A=[list(map(int,input().split()))[::-1] for i in range(n)]

day=0
zan=[n-1]*n
zann=sum(zan)

while True:
  day+=1
  sumi=set(range(n))
  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)
    


### FIXED CODE ###

n=int(input())

A=[list(map(int,input().split()))[::-1] for i in range(n)]

day=0
zan=[n-1]*n
zann=sum(zan)
sumi=set(range(n))

while True:
  day+=1

  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)
### BUGGY CODE ###

n = int(raw_input())
ls = [[] for i in range(12)]
for i in range(n):
    inp = raw_input()
    if inp[0] == "i":
        ls[len(inp[7:])].append(inp[7:])
    else:
        print "yes" if inp[5:] in ls[len(inp[5:])] else "no"
            

### FIXED CODE ###

n = int(raw_input())
ls = {}
for i in range(n):
    inp = raw_input()
    if inp[0] == "i":
        ls[inp[7:]] = 1
    else:
        try:
        	if ls[inp[5:]]: print "yes"
        except:
        	print "no"
### BUGGY CODE ###

from functools import reduce
S = list(map(int,input().rstrip()))
l=len(S)
result=0
for i in range(0,int(l-3)):
    for j in range(i+4,int(l+1)):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %673==0:
            if n%3==0:
                result+=1
print(result)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
P = [i-1 for i in P]
ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-(i+1))//l
            now += tot*e
        ans = max(ans,now)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = [int(t) - 1 for t in input().split()]
C = list(map(int,input().split()))

ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-(i+1))//l
            now += tot*e
        if ans < now:
            ans = now
print(ans)
### BUGGY CODE ###

input_data = input().split()

k=int(input_data[0])+1
s=int(input_data[1])
count=0

for i in range(k):
  for j in range(k):
    for u in range(k):
      if i + j + u == s:
        count= count +1
      else:
        pass

print(count)

### FIXED CODE ###

input_data = input().split()

k=int(input_data[0])
s=int(input_data[1])
count=0

for i in range(k+1):
  for j in range(k+1):
    z = s - i - j
    if (0 <= z and z <= k):
      count= count +1
    else:
      pass

print(count)
### BUGGY CODE ###

from sys import stdin, stdout
def gmi(): return map(int, stdin.readline().strip().split())
def gms(): return map(str, stdin.readline().strip().split())
def gari(): return list(map(int, stdin.readline().strip().split()))
def gars(): return list(map(int, stdin.readline().strip().split()))
def gs(): return stdin.readline().strip()
def gls(): return list(stdin.readline())
def gi(): return int(stdin.readline())

n = gi()
ar = gari()
c = 0
ans = 0
for i in ar[:-1]:
    c += 1
    for j in ar[c:]:
        ans += i*j
print(ans%1000000007)








### FIXED CODE ###

from sys import stdin, stdout
def gmi(): return map(int, stdin.readline().strip().split())
def gms(): return map(str, stdin.readline().strip().split())
def gari(): return list(map(int, stdin.readline().strip().split()))
def gars(): return list(map(int, stdin.readline().strip().split()))
def gs(): return stdin.readline().strip()
def gls(): return list(stdin.readline())
def gi(): return int(stdin.readline())

n = gi()
ar = gari()
c = 0
ans = 0
s = sum(ar)
sub = 0
for i in ar[:-1]:
    sub +=  ar[c]
    ans += i*(s-sub)
    c += 1
print(ans%1000000007)
### BUGGY CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.array(list(map(int, input().split())), dtype='uint')

    for i in range(n):
        print(np.count_nonzero(a == i+1))


if __name__=="__main__":
    main()


### FIXED CODE ###

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

    mem = [0] * n
    for i in range(n-1):
        mem[a[i]-1] += 1

    for i in mem:
        print(i)

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

s = input()
ans = 0

for i in range(len(s) - 3): 
    for j in range(i + 4, len(s) + 1):
        sub_s = int(s[i:j])
        if sub_s % 2019 == 0: ans += 1
print(ans)

### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2
print(ans)
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
sumpro = 0

for i in range(n-1):
    for j in range(i+1, n):
            sumpro += (a[i]*a[j])%mod
            if sumpro > mod:
                sumpro = sumpro%mod
print(sumpro)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
A = [-a for a in A]
B = sorted(list(map(int, input().split())), reverse=True)
B = [-b for b in B]
C = sorted(list(map(int, input().split())), reverse=True)
C = [-c for c in C]

unchecked = {}

h = []
heapq.heappush(h, (A[0]+B[0]+C[0], 0, 0, 0))
counter = 0
while counter < K:
    val, i, j, k = heapq.heappop(h)
    if unchecked.setdefault("{},{},{}".format(i, j, k), True):
        unchecked["{},{},{}".format(i, j, k)] = False
        print(- val)
        counter += 1
    if i+1 < X:
        heapq.heappush(h, (A[i+1] + B[j] + C[k], i+1, j, k))
    if j+1 < Y:
        heapq.heappush(h, (A[i] + B[j+1] + C[k], i, j+1, k))
    if k+1 < Z:
        heapq.heappush(h, (A[i] + B[j] + C[k+1], i, j, k+1))

### FIXED CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
A = [-a for a in A]
B = sorted(list(map(int, input().split())), reverse=True)
B = [-b for b in B]
C = sorted(list(map(int, input().split())), reverse=True)
C = [-c for c in C]

checked = []

h = []
heapq.heappush(h, (A[0]+B[0]+C[0], 0, 0, 0))
for _ in range(K):
    val, i, j, k = heapq.heappop(h)
    print(- val)
    if i+1 < X and (i+1, j, k) not in checked:
        heapq.heappush(h, (A[i+1] + B[j] + C[k], i+1, j, k))
        checked.append((i+1, j, k))
    if j+1 < Y and (i, j+1, k) not in checked:
        heapq.heappush(h, (A[i] + B[j+1] + C[k], i, j+1, k))
        checked.append((i, j+1, k))
    if k+1 < Z and (i, j, k+1) not in checked:
        heapq.heappush(h, (A[i] + B[j] + C[k+1], i, j, k+1))
        checked.append((i, j, k+1))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce, partial
import sys


def input():
    return sys.stdin.readline()[:-1]

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

def func(a, b, l):
	mod = 10**9 + 7
	return (a +  l*modinv(b, mod)) % mod

def func1(a, b, l):
	mod = 10**9 + 7
	return (a + l//b) % mod

def modinv(a, b):
	return pow(a,b-2,b)

def main():
	mod = 10**9 + 7
	N = int(input())
	A = tuple(map(int, input().split()))

	l = reduce(lcm, A) #% mod
	A = (0,) + A
	
	ans = reduce(partial(func1, l=l), A)
	print(ans)
	

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

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


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n , m = map(int, input().split())

root = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    root[a-1].append(b)
    root[b-1].append(a)

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)


### FIXED CODE ###

n , m = map(int, input().split())

root = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    root[a-1].append(b)
    root[b-1].append(a)

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
counter  = [0] * Q
for i in range(Q):
    l, r=map(int, input().split())
    for j in range(r-l):
        if S[l+j-1] == 'A' and S[l+j] == 'C':
            counter[i] += 1
for k in range(Q):
    print(counter[k])



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
ans = [0] * Q
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	ans[i] = t[r-1] - t[l-1]
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
lists = list(map(int,input().split()))
count = 0
old = 0
while(True):
    for i in range(n):
        if(lists[i] % 2 ==0):
            lists[i] = lists[i]/2
            count+=1
        else :
            lists[i] = lists[i]*3
    if(count == old):
        break
    old = count
print(count)

### FIXED CODE ###

n = int(input())
lists = list(map(int,input().split()))
count = 0

for i in range(n):
    if(lists[i] % 2 ==0):
        while(True):
            if(lists[i] % 2 ==0):
                lists[i] = lists[i]/2
                count+=1
            else :
                break
print(count)
### BUGGY CODE ###

N = int(input())
J = list(map(int,input().split()))
K = list(map(int,input().split()))
L = list(map(int,input().split()))
S = 0
k = 0
l = 0
for i in range(N):
  for p in range(N):
    if K[i] > J[p]:
      k += 1
  for q in range(N):
    if K[i] < L[q]:
      l += 1
  S += k*l
  k = 0
  l = 0
print(S)

### FIXED CODE ###

import bisect
N = int(input())
J = list(map(int,input().split()))
K = list(map(int,input().split()))
L = list(map(int,input().split()))
J.sort()
K.sort()
L.sort()
S = 0
for i in range(N):
  k = bisect.bisect_left(J,K[i])
  l = N - bisect.bisect_right(L,K[i])  
  S += k*l
print(S)
### BUGGY CODE ###

N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
l = [-1 for i in range(L)]
for i in range(N):
    l[L//N*i] = ord(S[i])-97
for i in range(M):
    if l[L//M*i] == -1:
        l[L//M*i] = ord(T[i])-97
    elif l[L//M*i] == ord(T[i])-97:
        pass
    else:
        flag = False
if flag:
    print(L)
else:
    print(-1)


### FIXED CODE ###

N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
def gcd(a, b): # 最大公約数
    while b:
        a, b = b, a % b
    return a

flag = True
for i in range(gcd(N,M)):
    if S[i*N//gcd(N,M)] == T[i*M//gcd(N,M)] and flag:
        pass
    else:
        flag = False
if flag:
    print(L)
else:
    print(-1)
### BUGGY CODE ###

n, p = map(int, input().split())
s = list(input())

if p in [2, 5]:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
    exit()

x = [0] * p
x[0] = 1
for i in range(n-1, -1, -1):
    x[int(''.join(s[i:])) % p] += 1

ans = 0

for z in x:
    ans += z * (z-1) // 2

print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
s = list(map(int, list(input())))

if p in [2, 5]:
    ans = 0
    for i, x in enumerate(s):
        if x % p == 0:
            ans += i + 1
    print(ans)
    exit()

x = [0] * p
x[0] = 1
temp = 0
d = 1
for i in range(n-1, -1, -1):
    temp = (temp + s[i] * d) % p
    x[temp] += 1
    d = (d * 10) % p

ans = 0

for z in x:
    ans += z * (z-1) // 2

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

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
A = [10**18] * 3
B = [10**18] * 3
dg = abs(ga - gb)
ds = abs(sa - sb)
db = abs(ba - bb)
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    res = -1
    for i in range(N+1):
        if X[0] * i > N:
            break
        M = N - X[0] * i
        jj = M // X[1]
        x = 200
        for j in range(max(jj - x, 0), jj+1):
            k = (M - X[1] * j) // X[2]
            res = max(res, dg * i + ds * j + db * k)
        kk = M // X[2]
        for k in range(max(kk - x, 0), kk+1):
            j = (M - X[2] * k) // X[1]
            res = max(res, dg * i + ds * j + db * k)
    return res

N += calc(A)
N += calc(B)
print(N)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
INF = 10**18
A = [INF] * 3
B = [INF] * 3
values = [abs(ga - gb), abs(sa - sb), abs(ba - bb)]
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    dp = [0] * (N+1)
    dp[0] = 0
    for x, v in zip(X, values):
        for i in range(N+1-x):
            dp[i+x] = max(dp[i+x], dp[i] + v)
    return dp[-1]

N += calc(A)
N += calc(B)
print(N)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    while len(a)>i:
        if a[i]!=i+1 and a!=[]:
            a=a[:i]+a[i+1:]
        else:
            break
    if a==list(range(1,i+1)) or a==[]:
        #print('Yay!')
        break
#print(a)
print(n-len(a) if a!=[] else -1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=1
for i in a:
    if i==p:
        p+=1
print(n-p+1 if p!=1 else -1)