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

def solve(way, height, n):
  ans = [i for i in range(n)]
  for a,b in way:
    if height[a-1] == height[b-1]:
      remove_1 = a-1
      remove_2 = b-1
      if remove_1 in ans:
        ans.remove(a-1)
      if remove_2 in ans:
        ans.remove(b-1)
    else:
      remove_idx = a if height[a-1] < height[b-1] else b
      remove_idx = remove_idx -1
      if remove_idx in ans:
        ans.remove(remove_idx)
  return len(ans)
 
 
if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))

### FIXED CODE ###

def solve(way, height, n):
  ss = []
  for a,b in way:
    if height[a-1] <= height[b-1]:
      ss.append(a)
    if height[a-1] >= height[b-1]:
      ss.append(b)
  return n - len(set(ss))


if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
mass = np.array([(0, 0) for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        mass[a] = [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])


### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
x = [0] * (num + 1)
y = [0] * (num + 1)
mp = [0] * (num + 1)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        x[a], y[a] = [i+1, j+1]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + abs(x[i] - x[i-d]) + abs(y[i] - y[i-d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])
### BUGGY CODE ###

if __name__ == '__main__':
    s = input()
    n = int(input())
    for _ in range(n):
        q = input().split()
        if q[0] == '1':
            s = s[::-1]
        else:
            if q[1] == '1':
                s = q[2]+s
            elif q[1] == '2':
                s = s+q[2]
    print(s)

### FIXED CODE ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    qs = [input() for e in range(n)]
    s = []
    e = []
    r = False
    for q in qs:
        if q == '1':
            r = not(r)
        elif q.startswith("2 1"):
            e.append(q[-1]) if r else s.append(q[-1])
        else:
            s.append(q[-1]) if r else e.append(q[-1])
    print("".join(e[::-1]) + d[::-1] + "".join(s) if r else "".join(s[::-1]) + d + "".join(e))
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


color, depth, graph = [], [], {}
def func(v, d, c):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return

    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    Q = int(input())
    q = []
    for _ in range(Q):
        v, d, c = map(int, input().split())
        q.append((v - 1, d, c))

    color = [0] * N
    depth = [0] * N
    for i in range(Q - 1, -1, -1):
        func(q[i][0], q[i][1], q[i][2])
    print(*color, sep="\n")

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


color, depth, graph = [], [], {}
def func(v, d, c):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return
    depth[v] = d
    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    Q = int(input())
    q = []
    for _ in range(Q):
        v, d, c = map(int, input().split())
        q.append((v - 1, d, c))

    color = [0] * N
    depth = [0] * N
    for i in range(Q - 1, -1, -1):
        func(q[i][0], q[i][1], q[i][2])
    print(*color, sep="\n")

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

n=int(input())
p=list(map(int,input().split()))
count=1
for i in range(1,n):
  if min(p[i],min(p[:i])) == p[i]:
    count+=1
print(count)



### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
count=0
q=100000000
for i in range(n):
  if min(p[i],q) == p[i]:
    count+=1
    q=p[i]
print(count)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0

while any(A[i] % 2 == 0 for i in range(n)):
    count = 0
    for i in range(n):
        if A[i] % 2 == 0:
            if count == 0:
                A[i] = A[i] // 2
                count += 1
            else:
                A[i] = A[i] * 3
        else:
            A[i] = A[i] * 3
    A.sort(reverse=True)
    ans += 1
        
print(ans)

### FIXED CODE ###

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

for i in range(n):
    if A[i] % 2 == 0:
        A2.append(A[i])
        
count = 0
for a in A2:
    while a % 2 == 0:
        a = a // 2
        count += 1
        
print(count)
### BUGGY CODE ###

n = int(input())
goods = []
for i in range(n):
  tmp = input()
  if tmp not in goods:
    goods.append(tmp)
print(len(goods))

### FIXED CODE ###

n = int(input())

goods = []
for i in range(n):
  goods.append(input())
  
s = set(goods)
print(len(s))
### BUGGY CODE ###

from bisect import bisect_right

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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[10**10]*30 for _ in range(n+1)]
dp[0][0] = 0


for j in range(min(n+1, 30)):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(min(n+1, 30)):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)


### FIXED CODE ###

from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

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

n = int(input())
d = dict()
s = [input() for i in range(n)]
l = []
for i in set(s):
    d[i] = 0
for i in s:
    d[i] += 1
l = [k for k, v in d.items() if v == max(d.values())]
l.sort()
print(*l, sep="\n")

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for i in range(n)]
c = Counter(s)
m = c.most_common()[0][1]
l = []
for i in c.keys():
    if c[i] == m:
        l.append(i)
l.sort()
print(*l, sep="\n")
### BUGGY CODE ###

import numpy

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

board = []

for l in range(H):
    line = list(map(int,input().split()))
    board.append(line)

board = numpy.reshape(board,(H,W))

trajectory = []
for i in range(H):
    for j in range(W):
        if i % 2 == 1:
            trajectory.append([i, W - 1 - j])
        else:
            trajectory.append([i,j])
            
trajectory = numpy.array(trajectory)

move = []

for index in range(len(trajectory) - 1):
    i, j = trajectory[index]
    ni, nj = trajectory[index + 1]
    
    if board[i][j] %2 == 1 and index < len(trajectory):
        board[i][j] += -1
        board[ni][nj] += 1
        move.append([i+1,j+1,ni+1,nj+1])
        
print(len(move))
for m in move:
    print(*m)

### FIXED CODE ###

import numpy

H, W = map(int,input().split())
board = [list(map(int,input().split())) for l in range(H)]

board = numpy.reshape(board,(H,W))
cboard = board.copy()

move = []

for i in range(H):
    for j in range(W-1):
        if board[i,j] % 2 == 1:
            board[i,j+1] += 1
            board[i,j] += -1
            move.append([i+1,j+1,i+1,j+2])
            
for i in range(H-1):
    if board[i,W-1] % 2 == 1:
        board[i,W-1] += -1
        board[i+1,W-1] +=1
        move.append([i+1,W,i+2,W])
        
print(len(move))
for m in move:
    print(*m)
### BUGGY CODE ###

N,K = map(int, input().split())
Ai = list(map(int, input().split()))
results= []

for i in range(0,N-K + 1):
    result = 1
    for j in range(i,K + i):
        result = result * Ai[j]
    results.append(result)

for i in range(0,N-K):
    if results[i + 1] > results[i]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

for i in range(0,N-K):

    if(Ai[i] < Ai[i+K]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

from collections import defaultdict
dp0 = defaultdict(lambda: 0)
dp1 = defaultdict(lambda: 0)
dp0[0] = 0
dp1[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    _dp0 = defaultdict(lambda: 0)
    _dp1 = defaultdict(lambda: 0)
    for k0,v0 in dp0.items():
        _dp0[k0] = max(_dp0[k0], v0)
        if k0+a < T:
            _dp0[k0+a] = max(_dp0[k0+a], v0+b)
        _dp1[k0] = max(_dp1[k0], v0+b)
    for k1,v1 in dp1.items():
        _dp1[k1] = max(_dp1[k1], v1)
        if k1+a < T:
            _dp1[k1+a] = max(_dp1[k1+a], v1+b)
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

a,b,k = map(int, input().split())

for i in range(k):
    if a >= 1:
        a -= 1
    else:
        b -= 1

print(a,b)

### FIXED CODE ###

a,b,k = map(int, input().split())

if a >= k:
    print(a-k, b)
elif b >= k-a:
    print(0, b-k+a)
else:
    print(0, 0)
### BUGGY CODE ###

N,*A=map(int,open(0).read().split())
m=1000000000+7
ans=0
for i in range(N):
    for j in range(i+1,N):
        ans+=(A[i]*A[j])
        ans%=m
print(ans)


### FIXED CODE ###

N,*A=map(int,open(0).read().split())
l=[]
s=0
for a in reversed(A):
    s+=a
    l.append(s)
l.reverse()
m=1000000000+7
ans=0
for i in range(N-1):
    ans+=A[i]*l[i+1]
    ans%=m
print(ans)
### BUGGY CODE ###

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

mod = 10**9 + 7

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = power_func(2,n,mod) - 1

a = comb_mod(n,a,mod)

b = comb_mod(n,b,mod)

ans = m - a - b

print(ans%mod)

### FIXED CODE ###

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

mod = 10**9 + 7

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

import math
def perm(n,r):
    return (math.factorial(n)//math.factorial(n-r))

s = comb(n,a,mod)
# print(s)

t = comb(n,b,mod)
# print(t)

ans = m - s - t

print(ans%mod)
### BUGGY CODE ###

A = [0] * (10**5)

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (int(X, 2) + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (int(X, 2) - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()
    cnt_init = X.count("1")
    x = int(X, 2)
    a = x % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            y = (a + pow(2, n - i - 1, cnt)) % cnt
        else:
            cnt = cnt_init - 1
            if cnt == 0:
                print(0)
                continue
            y = (b - pow(2, n - i - 1, cnt)) % cnt

        res = 1
        while y:
            cnt = bin(y).count("1")
            y %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = tuple(sorted(ab,key=itemgetter(0),reverse=True))
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = tuple(sorted(ab,key=itemgetter(0),reverse=True))
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))
### BUGGY CODE ###

from math import log10

def main(N):
    A = list(map(int, input().split()))
    st_A = set(A)
    if 0 in st_A:
        print(0)
    else:
        x = 1
        for a in A:
            x *= a
        if x > 10**18:
            print(-1)
        else:
            print(x)




if __name__ == '__main__':
    N = int(input())
    main(N)

### FIXED CODE ###

def main(N):
    A = list(map(int, input().split()))
    st_A = set(A)
    if 0 in st_A:
        print(0)
    else:
        x = 1
        for a in A:
            x *= a
            if x > 10 ** 18:
                print(-1)
                exit()
        else:
            print(x)





if __name__ == '__main__':
    N = int(input())
    main(N)
### BUGGY CODE ###

INF = float('inf')

N, K = map(int, input().split())
hs = list(map(int, input().split())) + [INF] * (K-1)

dp = [INF] * (N+K-1)
dp[0] = 0
for i in range(N-1):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(hs[i] - hs[i+j]))

print(dp[N-1])


### FIXED CODE ###

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

dp = [0] * N
for i in range(1, N):
    hi = hs[i]
    dp2 = dp[max(0, i-K):i]
    costs = [abs(h - hi) for h in hs[max(0, i-K):i]]
    dp[i] = min([dpj + cost for dpj, cost in zip(dp2, costs)])

print(dp[N-1])
### BUGGY CODE ###

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    black_list = set()
    ans = 0
    for a in sorted(A_dict.keys()):
        for b in black_list:
            if a % b == 0:
                break
        else:
            if A_dict[a] == 1:
                ans += 1
            black_list.add(a)
    print(ans)
main()

### FIXED CODE ###

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

    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    A_list = sorted(A_dict.keys())
    limit = A_list[-1]

    sieve = {i: True for i in A_dict.keys()}

    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):
            if i in sieve:
                sieve[i] = False

    print(sum([1 for i in sieve.keys() if sieve[i] and (A_dict[i]==1)]))
main()
### BUGGY CODE ###

from itertools import combinations
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10**9+7
ans = 0
for i in combinations(a,k):
    ans += i[k-1] - i[0]
    ans %= mod
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10**9+7
fac = [0]*(n+1)
finv = [0]*(n+1)
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac[0] = finv[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)
smin = 0
smax = 0
for i in range(n):
    smin += (a[i]*comb(n-i-1,k-1))%mod
    smin %= mod
    smax += (a[n-1-i]*comb(n-i-1,k-1))%mod
    smax %= mod
ans = (smax-smin)%mod
print(ans)
### BUGGY CODE ###

#ABC127-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
import bisect
n,m=IL()
A=IL()
A.sort()

for i in range(m):
    b,c=IL()
    s=bisect.bisect(A,c)
    
    if s<=b:
        A=[c]*s+A[s:]
    else:
        A=A[b:s]+[c]*b+A[s:]
           
print(sum(A))

### FIXED CODE ###

#ABC127-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
A=IL()
A.sort()
Q=[IL() for i in range(m)]
Q.sort(key=lambda x:-x[1])
j=0
for i in range(n):
    if Q[j][1]<A[i]:
        break
    else:
        Q[j][0]-=1
        A[i]=Q[j][1]
    if Q[j][0]==0:
        j+=1
    if j==m:
        break
print(sum(A))