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

import math, heapq
from operator import itemgetter
from collections import defaultdict
INF = float("inf")
MOD = int(1e9 + 7)

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

ab = sorted(AB)

v, que = 0, []
for n in range(1, M + 1):
    while ab:
        a, b = ab.pop(0)
        if a <= n:
            heapq.heappush(que, -b)
        else:
            ab.insert(0, (a, b))
            break
    if que:
        v += -heapq.heappop(que)
print(v)


### FIXED CODE ###

import math, heapq
from operator import itemgetter
from collections import defaultdict
INF = float("inf")
MOD = int(1e9 + 7)

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

    AB = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        AB[a].append(b)

    v, que = 0, []
    for m in range(1, M + 1):
        if m in AB:
            for b in AB[m]:
                heapq.heappush(que, -b)
        if que:
            v += -heapq.heappop(que)
    print(v)

main()
### BUGGY CODE ###

A, B, N = map(int, input().split())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]

if N < B:
    a = int(A * N / B)
    b = A * int(N / B)
    print(a - b)
    exit(0)

ans = 0
before_ans = 0
for i in range(1, N + 1):
    a = int(A * i / B)
    b = A * int(i / B)
    ans = max(ans, a - b)
    if before_ans > a - b:
        break
    # if ans == min(A - 1, B - 1):
    #    break
    before_ans = a - b
print(ans)


### FIXED CODE ###

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


# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
def solve(i):
    a = int(A * i / B)
    b = A * int(i / B)
    return a - b


print(solve(min(N, B - 1)))
### BUGGY CODE ###

from collections import defaultdict
import math
k= int(input())
ans = 0
dic = defaultdict(int)
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            if (a,b) not in dic:
                x = math.gcd(a,b)
                dic[(a,b)] = x
            x = dic[(a,b)]
            if (x,c) not in dic:
                x = math.gcd(x,c)
                dic[(x,c)] = x
            ans += dic[(x,c)]
print(ans)


### FIXED CODE ###

import math
k= int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        x = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(x,c)
print(ans)
### BUGGY CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
a = max(list)
for i in range(N):
    if list[i] == a:
        b = list[i]
        list[i] = 0
        print(max(list))
        list[i] = b
    else:
        print(a)


### FIXED CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
if sorted(list)[-1] == sorted(list)[-2]:
    list2 = [max(list)]*N
    print("\n".join(map(str,list2)))
else:
    list2 = [max(list)]*list.index(max(list))
    list2.append(sorted(list)[-2])
    list3 = [max(list)]*(N-list.index(max(list))-1)
    list2.extend(list3)
    print("\n".join(map(str,list2)))
### BUGGY CODE ###

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

ans=float('inf')
for i in range(n-k+1):
    nowx=x[i:i+k]
    if nowx[0]>=0 and nowx[-1]>=0:
        ans=min(ans, nowx[-1])
    elif nowx[0]<=0 and nowx[-1]<=0:
        ans=min(ans, abs(nowx[0]))
    elif nowx[0]<0 and nowx[-1]>=0:
        ans=min(ans, 2*abs(nowx[0])+nowx[-1], abs(nowx[0])+2*nowx[-1])
print(ans)

### FIXED CODE ###

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

ans=float('inf')
for i in range(n-k+1):
    nowx=(x[i],x[i+k-1])
    if nowx[0]>=0 and nowx[-1]>=0:
        ans=min(ans, nowx[-1])
    elif nowx[0]<=0 and nowx[-1]<=0:
        ans=min(ans, abs(nowx[0]))
    elif nowx[0]<0 and nowx[-1]>=0:
        ans=min(ans, 2*abs(nowx[0])+nowx[-1], abs(nowx[0])+2*nowx[-1])
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7
B0 = [0] * 60
B1 = [0] * 60
a = A.pop()
for b in range(60):
    if (a >> b) & 1:
        B1[b] += 1
    else:
        B0[b] += 1
ans = 0
for a in A:
    for b in range(60):
        if (a >> b) & 1:
            ans += (1 << b) * B0[b]
            B1[b] += 1
        else:
            ans += (1 << b) * B1[b]
            B0[b] += 1
        ans %= mod
print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array([int(_) for _ in input().split()], dtype=np.int64)
mod = 10**9 + 7
ans = 0
for b in range(60):
    B = (A >> b) & 1
    M = np.count_nonzero(B)
    ans += 2**b * M * (N - M)
    ans %= mod
print(ans)
### BUGGY CODE ###

import numpy as np

def main():
    N = int(input())
    A, B, C = np.full((3,N),0)

    for i in range(N):
        A[i], B[i], C[i] = [int(x) for x in input().split()]

    DP = np.full((N,3),0,dtype=int)

    act = [A,B,C]

    for i, X in enumerate(act):
        DP[0][i] = X[0]
    
    for i in range(N-1):
        for x, X in enumerate(act):
            for y, Y in enumerate(act):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+Y[i+1])

    print(DP[-1].max())

if __name__ == "__main__":
    main()
    pass

### FIXED CODE ###

def main():
    N = int(input())
    DP = [[0 for i in range(3)] for j in range(N+1)]
    
    for i in range(N):
        a = list(map(int, input().split()))
        for x in range(3):
            for y in range(3):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+a[y])
    print(max(DP[-1]))

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

from itertools import combinations
N = int(input())
A = tuple(map(int, input().split()))
print(sum(1 for i, j in combinations(range(N), 2) if A[i] > A[j]))



### FIXED CODE ###

INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            cnt += j
            i += 1
        else:
            A[k] = R[j]
            j += 1
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)
### BUGGY CODE ###

from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st =(st + int(i) * kai) % 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10
 
print(cou)

### FIXED CODE ###

from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st += int(i) * kai
  st %= 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10 % 2019

print(cou)
### BUGGY CODE ###

s = input()

N = len(s)

cnt = 0

for i in range(0,N):
	for j in range(i+4,N+1):
		if int(s[i:j]) % 2019 == 0:
			cnt = cnt + 1

print(cnt)


### FIXED CODE ###

from collections import Counter
s = input()[::-1]
T = [0]*(len(s)+1)
digit = 1

for i in range(1,len(s)+1):
    T[i] = (T[i-1]+digit*int(s[i-1]))
    T[i] = T[i] % 2019
    digit = digit * 10
    digit = digit % 2019

S = Counter(T)
ans = 0
for i in S.values():
    ans+=(i*(i-1))//2

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

x,y,z,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ab = []
for i in range(x):
  for j in range(y):
    tmp = a[i] + b[j]
    ab += [tmp]
ab.sort()
ab = ab[::-1][:k]
#print(ab)

ans = []
for i in range(len(ab)):
  for j in range(z):
    tmp = ab[i] + c[j]
    ans += [tmp]
ans.sort()
ans = ans[::-1][:k]
for i in ans:
  print(i)


### FIXED CODE ###

x,y,z,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ab = []
for i in range(x):
  for j in range(y):
    tmp = a[i] + b[j]
    ab += [tmp]
ab.sort()
ab = ab[::-1][:k]
#print(ab)

ans = []
for i in range(len(ab)):
  for j in range(z):
    tmp = ab[i] + c[j]
    ans += [tmp]
ans.sort()
ans = ans[::-1][:k]
for i in ans:
  print(i)
### BUGGY CODE ###

from collections import namedtuple


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n + 1)]
    self.size = [1] * (n + 1)

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)


### FIXED CODE ###

from collections import namedtuple


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n + 1)]
    self.size = [1] * (n + 1)

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)
### BUGGY CODE ###

import re
import numpy as np
n,q=map(int,input().split())
s=input()
a=np.zeros(n+1,dtype=int)
for m in re.finditer("AC", s):
  a[m.start()+2:]+=1

for _ in range(q):
  l,r=map(int,input().split())
  print(a[r]-a[l])


### FIXED CODE ###

import re
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
tmp=0
for i in range(n-1):
  if s[i:i+2]=="AC":
    tmp+=1
  a[i+2]=tmp

for _ in range(q):
  l,r=map(int,input().split())
  print(a[r]-a[l])
### BUGGY CODE ###

from collections import Counter

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

  # 書かれた番号の頻度
  Freq = Counter(A)

  # 答えのメモ (複数回計算しないように)
  memo = dict()

  for a in A:
    if memo.get(a) != None:
      print(memo[a])
      continue

    ans = 0
    for kv in Freq.items():
      # key -> value : 番号 -> ボール個数
      cnt = kv[1]
      # 自身は取り除く
      if kv[0] == a: cnt -= 1
      # 2個未満はスキップ
      if cnt < 2: continue
      # 2つ選ぶ方法は n*(n-1)//2
      ans += cnt * (cnt-1) // 2
    print(ans)
    memo[a] = ans

solve()

### FIXED CODE ###

from collections import Counter

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

# 書かれた番号の頻度
Freq = dict(sorted(Counter(A).items(), key=lambda x: x[1], reverse=True))

# 答えの最大値
ans_max = 0
for kv in Freq.items():
  ans_max += kv[1] * (kv[1] - 1) // 2

for a in A:
  # 1個しか存在しない番号は、取り除いても答えに影響しない
  if Freq.get(a) == 1:
    print(ans_max)
    continue

  # x個の場合と、x-1個の場合と、の差分
  x = Freq.get(a)
  diff = (x * (x-1) // 2) - ((x-1) * (x-2) // 2)

  # そのぶんだけ、答えの最大値から減らす
  ans = ans_max - diff
  print(ans)
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]):
                        answer = (x2-x1) * (y2-y1)

    print(answer)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= sum(map(lambda xy: (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2), xy_list)):
                        answer = (x2-x1) * (y2-y1)

    print(answer)
### BUGGY CODE ###

import math
import sys
def getN():
    return int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

def main():
    
    K = getN()

    result = 0

    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                result += gcd(gcd(i,j),k)
    
    print(result)

    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

def getN():
    return int(input())

# def gcd(p, q):
#     if p % q == 0: return q
#     return gcd(q, p % q)

def gcd(p, q):
    while q != 0:
        r = p % q
        p = q
        q = r
    return p

def main():
    
    K = getN()

    result = 0

    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                result += gcd(gcd(i,j),k)
    
    print(result)

    return

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

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

res = 0;
dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if S[i] == S[j]:
      dp[i][j] = max(dp[i][j], dp[i+1][j+1]+1);
    res = max(res, min(dp[i][j], j-i));
print(res)


### FIXED CODE ###

N = int(input())
S = input()
 
res = 0;
dp = [[0]*(N+1) for _ in range(N+1)]
 
for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if S[i] == S[j]:
      dp[i][j] = max(dp[i][j], dp[i+1][j+1]+1);
    res = max(res, min(dp[i][j], j-i));
print(res)
### BUGGY CODE ###


import itertools

N, M, R = map(int, input().split())
rs = map(int, input().split())
rs = list(map(lambda x:x-1 , rs))
ABCs = [list(map(int, input().split())) for i in range(M)]

d = [[10**6] * N for i in range(N)]

for abc in ABCs:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k] = min(d[j][k], d[j][i] + d[i][k])
            
for i in range(N):
    d[i][i] = 10**6

kyori = []
narabi = list(itertools.combinations(rs,2))
for n in narabi:
    kyori.append(d[n[0]][n[1]])

if len(kyori) >= 2:
    z = max(kyori)
    print(sum(kyori) - z)
else:
    print(sum(kyori))


### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ARSP = [[float('inf')] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    ARSP[a][b] = c
    ARSP[b][a] = c


def warshall_floyd(adj_array):
    for k in range(len(adj_array)):
        for i in range(len(adj_array)):
            for j in range(len(adj_array)):
                if adj_array[i][k] + adj_array[k][j] < adj_array[i][j]:
                    adj_array[i][j] = min(adj_array[i][j], adj_array[i][k] + adj_array[k][j])
    return adj_array


ARSP = warshall_floyd(ARSP)

# 訪れ方の全列挙(max 8! = 40320)
journey = list(permutations(r))

ans = float('inf')
for j in journey:
    cost = 0
    for i in range(1, R):
        if ARSP[j[i]][j[i-1]] == float('inf'):
            break
        cost += ARSP[j[i]][j[i-1]]
        if cost >= ans:
            break
    else:
        ans = cost

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

import collections

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

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)):
    count_one_list[i] = new_S[:i].count('1')

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)

### FIXED CODE ###

import collections

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

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)
### BUGGY CODE ###

import itertools

N = int(input())
a = list(int(i) for i in input().split())

for k in range(3, N+1):
    for p in itertools.permutations(a, k):
        cnt=0
        for i in range(k):
            if i == 0:
                if p[k - 1] ^ p[i + 1] != p[i]:
                    break
            elif i == k - 1:
                if p[i - 1] ^ p[0] != p[i]:
                    if len(p) -1 == cnt:
                        print("No")
                        exit()
                    break
                else:
                    a = (set(a) - set(p))
                    a.add(p[i - 1])
                    a.add(p[0])
                    if k == N:
                        print("Yes")
                        exit()
            else:
                if p[i - 1] ^ p[i + 1] != p[i]:
                    break
        cnt =cnt+1
print("No")

### FIXED CODE ###

a = [input() for i in range(2)]
 
N = int(a[0])
data = a[1].split(' ')
 
data = [int(i) for i in data]
 
result = []
a = 0
for i in range(N):
    a = a ^ data[i]
    
if a == 0:
    print('Yes')
    exit()
    
print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    CSF = []
    for i in range(N-1):
        c, s, f = map(int, input().strip().split())
        CSF.append((c, s, f))
    return N, CSF


def solve(N, CSF, SMAX=200000):
    dp = [[0 for t in range(SMAX)] for i in range(N)]
    for i in range(N):
        dp[i][0] = 1
    for i in range(N-1):
        c, s, f = CSF[i]
        for t in range(s, SMAX-c, f):
            if t == s:
                dp[i+1][t+c] = sum(dp[i][:t+1])
            else:
                dp[i+1][t+c] = sum(dp[i][t-f+1:t+1])
    ans = []
    for t in range(SMAX):
        while dp[N-1][t] > 0:
            ans.append(t)
            dp[N-1][t] -= 1
    for a in ans[::-1]:
        print(a)



if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    CSF = []
    for i in range(N-1):
        c, s, f = map(int, input().strip().split())
        CSF.append((c, s, f))
    return N, CSF


def solve(N, CSF, SMAX=200000):
    A = []
    for c, s, f in CSF:
        for i in range(len(A)):
            if A[i] % f == 0:
                A[i] = max(A[i], s) + c
            else:
                A[i] = max(A[i] - A[i] % f + f, s) + c
        A.append(s + c)
    A.append(0)
    for a in A:
        print(a)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    #初期値は0
    def Num(dest):
        q=dest-1
        if flog[q]>0:
            return flog[q]
        if dest<k+2:
            res=abs(h[q]-h[0])
            flog[q]=res
            return res
        
        min=Num(q)+abs(h[q]-h[q-1])
        for i in range(2,k+1):
            tmp=Num(dest-i)+abs(h[q]-h[q-i])
            if min>tmp:
                min=tmp
        flog[q]=min
        return min   
    print(Num(n))
if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

S=1
Q=[]
for i in range(K):
    S=S*A[i]
Q.append(S)
for i in range(N-K):
    S=S/A[i]*A[K+i]
    Q.append(S)
    
for i in range(len(Q)-1):
    if Q[i]<Q[i+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(N-K):
    if A[i+K]>A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import heapq
import sys
input=sys.stdin.readline
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    heapq.heapify(a)

    for i in range(m):
        b,c=map(int,input().split())
        for j in range(b):
            temp=heapq.heappop(a)
            if temp<c:
                heapq.heappush(a,c)
            else:
                heapq.heappush(a,temp)
                break
    print(sum(a))

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[list(map(int,input().split())) for i in range(m)]
bc=sorted(bc,reverse=True,key=lambda x:x[1])
c=[]

cnt=0
for B,C in bc:
    for i in range(B):
        if cnt==n:break
        cnt+=1
        c.append(C)
c=sorted(c,reverse=True)

ans=sum(a)
temp=ans
for i in range(n):
    if cnt<=i:continue
    temp+=-a[i]+c[i]
    if temp>ans:ans=temp
print(ans)
### BUGGY CODE ###

n= int(input().strip())
a= list(map(int, input().strip().split()))
x=0
for i in range(n-1):
    for j in range(i+1,n):
        x+=(a[i]*a[j])%(10**9+7)
        if x>=10**9+7:
            x=x%(10**9+7)
print(x)

### FIXED CODE ###

n= int(input().strip())
a= list(map(int, input().strip().split()))
x=0
A=0

for i in range(n):
    A+=a[i]
x=0
for i in range(n):
    x+=a[i]*(A-a[i])
x=x//2
x=x%(10**9+7)
print(x)
### BUGGY CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
Ds = []
for i in range(M):
    B, C = map(int, input().split())
    D = [C] * B
    Ds.extend(D)

Ds.sort(reverse=True)
s = min([N, len(Ds)])
As.sort()
for i in range(s):
    if As[i] < Ds[i]:
        As[i] = Ds[i]
    else:
        break

print(sum(As))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
adic = {}
for a in As:
    adic[a] = adic.get(a, 0) + 1

Ds = []
for a in adic:
    Ds.append([a, adic[a]])
for i in range(M):
    B, C = map(int, input().split())
    Ds.append([C,B])

Ds.sort(reverse=True)

count, sum = 0,0
for D in Ds:
    c = D[1] if D[1] + count <= N else N - count
    sum += c * D[0]
    count += c
    if count == N:
        break

print(sum)