Harryxun/stf_run huggingface dataset:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

if K < 10:  # 1桁の数はすべてlun_lun
    print(K)
else:  # 桁数の小さいものからlun_lun数を生成し，queueに加えていく
    dq = deque([i for i in range(1, 10)])
    count = 0
    while True:
        x = dq.popleft()
        count += 1
        if count == K:
            print(x)
            return
        d = x % 10
        if d != 0:
            dq.append(10 * x + d - 1)
        dq.append(10 * x + d)
        if d != 9:
            dq.append(10 * x + d + 1)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

if K < 10:  # 1桁の数はすべてlun_lun
    print(K)
else:  # 桁数の小さいものからlun_lun数を生成し，queueに加えていく
    dq = deque([i for i in range(1, 10)])
    count = 0
    while True:
        x = dq.popleft()
        count += 1
        if count == K:
            print(x)
            exit()
        d = x % 10
        if d != 0:
            dq.append(10 * x + d - 1)
        dq.append(10 * x + d)
        if d != 9:
            dq.append(10 * x + d + 1)
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    P = il()
    cnt = 0
    for n in range(N):
        if P[n] != n + 1:
            cnt += 1
        if P[P[n]] != n+1:
            print('NO')
            exit()
    print('NO' if cnt > 3 else 'YES')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    P = il()
    Q = [n+1 for n in range(N)]

    cnt = 0
    for p, q in zip(P, Q):
        if p != q and P[p-1] != q:
            print('NO')
            exit()
        elif p != q:
            cnt += 1
    else:
        if cnt/2 < 2: print('YES')
        else: print('NO')


if __name__ == '__main__':
    main()
a=map(int,input().split());print(sum(a)+9*max(a))

### FIXED CODE ###

a=list(map(int,input().split()));print(sum(a)+9*max(a))
N = int(input())
print(int(N*(N-1)/2))

### FIXED CODE ###

S = input()
T = input()
count = 0

for i in range(len(S)):
  if S[i]==T[i]:
    count += 1
    
print(count)
H, W, D = map(int, input().split())

dic = {}


def magic_test(L, R, power):
    if L == R:
        return power
    x, y = dic[L]
    nx, ny = dic[L+D]
    power += abs(x-nx) + abs(y-ny)
    return magic_test(L+D, R, power)


for y in range(1, H+1):
    A = list(map(int, input().split()))

    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = magic_test(L, R, 0)
    print(ans)


### FIXED CODE ###

H, W, D = map(int, input().split())

dic = {}
K = H*W//D
memo = [[0]* (K+1) for _ in range(D+1)]

for y in range(1, H+1):
    A = list(map(int, input().split()))
    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

for extra in range(H*W+1, H*W+2*D):
    dic[extra] = [0, 0]

for i in range(1, D+1):
    for j in range(K):
        x, y = dic[i+D*j]
        nx, ny = dic[i+D*(j+1)]
        cost = abs(x-nx) + abs(y-ny)
        memo[i][j+1] = memo[i][j] + cost

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    j = L//D
    delta = (R-L)//D
    if i == 0:
        i = D
        j -= 1
    ans = memo[i][j+delta] - memo[i][j]
    print(ans)
mod = 7+10**9
def ncr(n,c,mod):
  x = 1
  y = 1
  for i in range(n-c+1,n+1):
    x = x*i%mod
  for j in range(1,c+1):
    y = y*j%mod
  return (x * pow(y, mod-2, mod)) % mod

n, a, b = map(int, input().split())
al = pow(2, n, mod) -1
acr = ncr(n, a, mod)
bcr = ncr(n, b, mod)
print((al-(acr+bcr))%mod

### FIXED CODE ###

mod = 7+10**9
def ncr(n,c,mod):
  x = 1
  y = 1
  for i in range(n-c+1,n+1):
    x = x*i%mod
  for j in range(1,c+1):
    y = y*j%mod
  return (x * pow(y, mod-2, mod)) % mod

n, a, b = map(int, input().split())
al = pow(2, n, mod) -1
acr = ncr(n, a, mod)
bcr = ncr(n, b, mod)
print( (al-(acr+bcr))%mod )
A=list(map(int,input.split()))
s=A[0]
w=A[1]

if s>w:
    print(safe)
else:
    print(unsafe)

### FIXED CODE ###


s,w=map(int,input().split())


if s>w:
    print("safe")
else:
    print("unsafe")
import sys

for line in sys.stdin:
    A=line.split()
    B=map(int,A)

B=B.sort()

while B[1]%B[0] != 0:
    C=B[0]
    B[0]=B[1]%B[0]
    B[1]=C

print B[0]

### FIXED CODE ###

A=map(int,raw_input().split())
A.sort()

while A[1]%A[0]!=0:
    temp=A[0]
    A[0]=A[1]%A[0]
    A[1]=temp

print A[0]
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    A=LLIN(H)
    odds=[]
    ans=[]
    for i in range(H):
        if i&1:
            for j in range(W)[::-1]:
                if A[i][j]&1:
                    if j==0:
                        dy=1
                        dx=0
                    else:
                        dy=0
                        dx=-1
                    if i+dy!=H:
                        
                        ans.append((i+1,j+1,i+dy+1,j+dx+1))
                        A[i+dy][j+dx]+=1
        else:
            for j in range(W)[::-1]:
                if A[i][j]&1:
                    if j==W-1:
                        dy=1
                        dx=0
                    else:
                        dy=0
                        dx=1
                    if i+dy!=H:
                       
                        ans.append((i+1,j+1,i+dy+1,j+dx+1))
                        A[i+dy][j+dx]+=1

    print(len(ans))
    for a in ans:
        print(*a)
    


if __name__ == '__main__':
　　main

### FIXED CODE ###

A, B = map(int, input().split())
if 2 not in [A, B]:
    print("Yes")
else:
    print("No")
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        i, j = dx_dy[i][0], dx_dy[i][1]
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])


### FIXED CODE ###

from collections import deque


h, w = map(int,input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch, cw)])
S = [[float("inf")]*w for _ in range(h)]
S[ch][cw] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = ((1,0),(0,1),(-1,0),(0,-1))
    ans = S[y][x]

    if (y, x) == (dh, dw):
            S[y][x] = ans
            break

    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h and S[y+j][x+i] > ans and G[y+j][x+i] == ".":
            queue.appendleft((y+j, x+i))
            S[y+j][x+i] = ans
            

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= x+i < w and 0 <= y+j < h and S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.append((y+j, x+i))


if S[dh][dw] == float("inf"):
    print(-1)
else:
    print(S[dh][dw])
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for l in range(H)]
b=[]
d=[]
for m in range(len(c)):
  for item in c[m]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    b.append(item_mod)
  d.append(b)
  b=[]

C_arr = np.array(d , dtype = int64)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertools.product([0,1] , repeat=W)))
 
ans = 0
for i in range(len(In)):
  for j in range(len(Out)):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

### FIXED CODE ###

H, W, K = list(map(int, input().split()))
 
c = [list(input()) for i in range(H)]
 
cnt = 0
for i in range(2**H):
    for j in range(2**W):
        cnt_black = 0
        for k in range(H):
            if (i >> k) & 1:
                continue
            for l in range(W):
                if (j >> l) & 1:
                    continue
                if c[k][l] == '#':
                    cnt_black += 1
        if cnt_black == K:
            cnt += 1
 
print(cnt)
a , b = map(int , input().split)
c=str(a)+str(b)
c=int(c)
print(c)
for i in range (100):
    if c!= int(i^2):
        print("Yes")  
        break      
    elif c==100:
        print("No")
        break

        

### FIXED CODE ###

a , b = map(int , input().split())
c=str(a)+str(b)
c=int(c)
for i in range (1000):
    if c== int(i*i):
        print("Yes")  
        break      
    elif i==1000-1:
        print("No")
        break
n = int(input())
h = list(map(int, input().split()))
sv = h[n-1]
ok = True
for i in range(n-1):
    if h[i] - sv - 1 >= 2:
        ok = False

if ok:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a, b, c = map(int, input().split())
if a - b < c:
    ans = c - (a - b)
else:
    ans = 0

print(ans)
N = int(input())
S = input()

c = Counter(S)
print(max(0, c["#"] - 1))

### FIXED CODE ###

from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

N = int(input())
S = input()

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

l = 0
r = c["."]

for i in range(0, N):

    if S[i] == "#":
        l += 1
    else:
        r -= 1
    a = l + r
    if mi > a:
        mi = a

print(min(mi, A, B))
n,a,b=map(int,input().split())

t=1000000007

def mod(k):
    return k%t

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

base=power_func(2,n,t)
    
print(mod(2*t+base-1-comb(n,a,t)-comb(n,b,t)))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
sum=0
for i in range(N):
    sum = sum+A[i]
ans = 0
if sum%N <= N//2:
    for i in range(N):
        ans = ans+ (A[i]-(sum//N))**2
    print(ans)
else:
    for i in range(N):
        ans = ans+ (A[i]-1-(sum//N))**2
    print(ans)
n,a = map(int,input().split())
print(n*n-a)

### FIXED CODE ###

n = int(input())
a = int(input())
print(n*n-a)
a, b, c = list(map(int, input().split()))
if a >= b && a >= c:
    print(10*a + b + c)
elif b >= a && b >= c:
    print(10*b + a + c)
else:
    print(10*c + a + b)   

### FIXED CODE ###

a, b, c = list(map(int, input().split()))
if a >= b and a >= c:
    print(10*a + b + c)
elif b >= a and b >= c:
    print(10*b + a + c)
else:
    print(10*c + a + b)
try:
	lines = []
	while True:
		lines.append(map(int, input().split(' ')))
except EOFError:
	for i in range(len(lines)):
		sums = lines[i][0] + lines[i][1]
		print(len(str(sums)))

### FIXED CODE ###

import sys
L = sys.stdin.readlines()
for line in L:
	N = line[:-1].split(' ')
	sums = int(N[0]) + int(N[1])
	print(len(str(sums)))
from fractions import Fraction
import math

n = int(input())
num = list(map(int, input().split()))
num = [ Fraction(i) for i in num ]

if 0 in num:
    print(0)
elif len([i for i in num if i >= 10**18]) != 0:
    print(-1)
else:
    mult = math.prod(num)
    if mult > 10**18:
        print(-1)
    else:
        print(int(mult))

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
input(int(N))
print(N**3)

### FIXED CODE ###

N = input()
print(int(N)**3)
# -*- coding: utf-8 -*-
r = int(input().strip())
p = 3.14159265
m = r * r * p
l = 2 * r * p
print("{0:.6f} {1:.6f}".format(m,l))

### FIXED CODE ###

# -*- coding: utf-8 -*-
r = float(input().strip())
p = 3.141592653589793238
m = r * r * p
l = 2 * r * p
print("{0:.6f} {1:.6f}".format(m,l))
n,k = map(int,input().split())
h_list = [int(input()) for _ in range(n)]
h_list.sort()
i = 0
j = k-1
ans = 10**9

while j <= n:
    diff = abs(h_list[i]-h_list[j])
    ans = min(ans,diff)
    i  = j
    j += k-1
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
h_list = [int(input()) for _ in range(n)]
h_list.sort(reverse=True)
i = 0
j = k-1
ans = 10**9

while j < n:
    diff = h_list[i]-h_list[j]
    ans = min(ans,diff)
    i += 1
    j += 1
print(ans)
n=input()
p=input()

n=int(n[0])
p=p.split()
p=[int(p) for p in p]

output=0
for i in range(n-2):
    if p[i]<p[i+1] and p[i+1]<p[i+2]:
        output=output+1
    elif p[i+2]<p[i+1] and p[i+1]<p[i]:
        output=output+1
    else:
        output=output+0
    
print(output)

### FIXED CODE ###

input_data=input()
 
a=input_data[0]
b=input_data[1]
c=input_data[2]
d=input_data[3]
 
if a==b :
    if c==d and a!=c :
            output="Yes"
    else :
        output="No"
    
else :
        if a==c and b==d :
            output="Yes"
    
        elif a==d and b==c :
            output="Yes"
        
        else :
            output="No"
           
print(output)
import sys

(sn, sm) = sys.stdin.readline().split()
n = int(sn)
m = int(sm)

flg = [0 for j in range(m)]
for i in range(n):
  sa = sys.stdin.readline().split()
  for saj in sa:
    aj = int(saj)
    flg[aj - 1] += 1

suma = 0
for sumaj in range(flg):
  if sumaj == n:
    suma += 1
print(suma)

### FIXED CODE ###

import sys

(sn, sm) = sys.stdin.readline().split()
n = int(sn)
m = int(sm)

flg = [0 for j in range(m)]
for i in range(n):
  sa = sys.stdin.readline().split()
  if len(sa) > 1:
    for saj in sa[1:]:
      aj = int(saj)
      flg[aj - 1] += 1

suma = 0
for sumaj in flg:
  if sumaj == n:
    suma += 1
print(suma)
# 塩基 A, C, G, T が存在し、A と T、C と G がそれぞれ対

b = input()

if b == ('A'):
    print(T)

elif b == ('C'):
    print(G)

elif b == ('T'):
    print(A)

elif b == ('G'):
    print(C)


### FIXED CODE ###

# 塩基 A, C, G, T が存在し、A と T、C と G がそれぞれ対

b = input()

if b == ('A'):
    print('T')

if b == ('C'):
    print('G')

if b == ('T'):
    print('A')

if b == ('G'):
    print('C')
import numpy as np
n,m = map(int,input().split())
penalty = np.zeros(n)
done = np.zeros(n)
for i in range(m):
    p,s = input().split()
    p = int(p)
    if s == 'WA':
        if done[p-1]==0:
            penalty[p-1] +=1
    else:
        done[p-1]=1
penalty = penalty*done
print(int(sum(done)),int(sum(penalty)))

### FIXED CODE ###

n,m = map(int,input().split())
penalty = [0]*n
did = [0]*n
for i in range(m):
    p,s = input().split()
    p = int(p)
    if s == 'WA':
        if did[p-1]==0:
            penalty[p-1] +=1
    else:
        did[p-1]=1
for i in range(n):
    penalty[i]*=did[i]
print(sum(did),sum(penalty))
n = int(input())
a = list(map(int, (input().split())))
a.append(0)
mon = 1000
kab = 0
x = 0
z = 0
while z <= n-1:
    if x == 0:
        while a[z+1] < a[z]:
            z += 1
            if z == n-1:
                break
        kab += mon//a[z]
        ans = mon
        mon -= kab*a[z]
        x = 1
        if z < n-1:
            z += 1
        else:
            break
    elif x == 1:
        while a[z+1] > a[z]:
            z += 1
            if z == n-1:
                break
        mon += kab*a[z]
        kab = 0
        x = 0
        if z < n-1:
            z += 1
        else:
            break
print(max(ans, mon))

### FIXED CODE ###

n = int(input())
a = list(map(int, (input().split())))
a.append(0)
mon = 1000
kab = 0
x = 0
for i in range(n):
    if a[i] <= a[i+1]:
        kab = mon//a[i]
        mon += kab*(a[i+1]-a[i])
print(mon)
def main(A,D,N):
    for i in range(N):
        if A[i]>D[i]:
            return sum(D[:i]+A[i:])
    return sum(D)

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
CB=[]
for m in range(M):
    b,c=map(int,input().split())
    CB.append([c,b])
CB.sort()
CB=CB[::-1]
D=[]
while len(D)<N:
    D.append(CB[0][0])
    CB[0][1]-=1
    if CB[0][1]==0:
        CB.remove(CB[0])
for bc in BC:
    B+=[bc[0]]*bc[1]
print(main(A,B,N))

### FIXED CODE ###

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

BC=[]
for m in range(M):
    b,c=map(int,input().split())
    BC.append([b,c])

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

D=[]
for [b,c] in BC:
    D+=[c]*b
    if len(D)>N:
        break

if len(D)<N:
    D+=[0]*(N-len(D))

AD=[max(A[i],D[i]) for i in range(N)]
 
print(sum(AD))
input = input().split()
A = [int(item) for item in input]
N = A.pop(0)

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

dp = [[H * W] * H] * W

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            min_num_h = H * W
        else:
            min_num_h = dp[i - 1][j] + (0 if HW_list[i][j] == HW_list[i - 1][j] else 1)
        if j == 0:
            min_num_w = H * W
        else:
            min_num_w = dp[i][j - 1] + (0 if HW_list[i][j] == HW_list[i][j - 1] else 1)
        dp[i][j] = min(min_num_h, min_num_w)

print(dp[H - 1][W - 1] // 2 + (1 if HW_list[0][0] == "#" or HW_list[H - 1][W - 1] == "#" else 0))

### FIXED CODE ###

# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

dp = [[H * W] * W] * H

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            min_num_h = H * W
        else:
            min_num_h = dp[i - 1][j] + (0 if HW_list[i][j] == HW_list[i - 1][j] else 1)
        if j == 0:
            min_num_w = H * W
        else:
            min_num_w = dp[i][j - 1] + (0 if HW_list[i][j] == HW_list[i][j - 1] else 1)
        dp[i][j] = min(min_num_h, min_num_w)

print(dp[H - 1][W - 1] // 2 + (1 if HW_list[0][0] == "#" or HW_list[H - 1][W - 1] == "#" else 0))