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

# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *

n, q = map(int, input().split())
events = []
heapify(events)
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    heappush(events, [s - x - 0.3, x, 1])
    heappush(events, [t - x - 0.7, x, 2])
for i in range(q):
    d = int(input())
    heappush(events, [d, i, 3])
for _ in range(n * 2 + q):
    j, h, s = heappop(events)
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
print(*ans,sep="\n")


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

n=int(input())
s=list(input())
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[j]!=s[i] and s[i]!=s[k] and s[j]!=s[k] and j-i!=k-j:
                ans = ans+1
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
a=s.count("R")
b=s.count("G")
c=s.count("B")
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    k=2*j-i
    if n-1>=k and (s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]): 
      ans=ans+1
print(a*b*c-ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                ans += 1

print(ans)

### FIXED CODE ###

k,s = map(int, input().split())
a = (s+2)*(s+1)/2
b = (s-k+1)*(s-k)/2
c = (s-2*k)*(s-2*k-1)/2

if s <= k:
    print(int(a))
elif s <= 2*k+1:
    print(int(a-3*b))
elif s <= 3*k:
    print(int(a-3*b+3*c))
### BUGGY CODE ###

K = int(input())
memo = {}
def gcd(x,y):
    if x < y:
        x,y = y,x
    if (x,y) in memo:return memo[(x,y)]
    if y == 0:return x
    memo[(x,y)] = gcd(y,x%y)
    return memo[(x,y)]
ans = 0
temp = []
for i in range(1,K+1):
    for j in range(1,K+1):
        temp.append(gcd(i,j))
for i in range(1,K+1):
    for num in temp:
        ans += gcd(i,num)
print(ans)

### FIXED CODE ###

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

import fractions
from functools import reduce


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


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


hA = [a//2 for a in A]
lcm = lcm_list(hA)

for a in A:
    if lcm % a == 0 or lcm > m:
        print(0)
        break
else:
    if (m//lcm) % 2 == 0:
        print(m//lcm//2)
    else:
        print(m//lcm//2 + 1)


### FIXED CODE ###

import fractions
from functools import reduce


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

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    for a in A:
        if lcm % a == 0:
            print(0)
            break
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    root = [1]
    ans = K
    while True:
        a = K - 2
        if root[0] == 1:
            a = K - 1
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if (0<=my<tate and 0<=mx<yoko) and maze[my][mx]=="." and visited[my][mx]>cnt:
                queue.append([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if (0<=my<tate and 0<=mx<yoko) and maze[my][mx]==".":
                    if visited[my][mx]>cnt+1:
                        queue.append([my,mx])
                        visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()




### FIXED CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.appendleft([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()
### BUGGY CODE ###

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

A = collections.Counter(A)
cnt = 0
while len(A.keys()) > K:
    k, v = min(A.items(), key=lambda x: x[1])
    cnt += v
    del A[k]
    
print(cnt)

### FIXED CODE ###

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

A = collections.Counter(A)
A = sorted(A.items(), key=lambda x:x[1])
cnt = A[:len(A)-K]

ans = []
for c in cnt:
    ans.append(c[1])
    
print(sum(ans))
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1,n+1):
	p *= i
p = p % (10**9+7)
print(p)

### FIXED CODE ###

n = int(input())
p = 1
for i in range(1,n+1):
	p *= i
	p = p % (10**9+7)
print(p)
### BUGGY CODE ###

n,k=map(int,input().split())
b=[int(input()) for _ in range(n)]
dp=[[0]*(max(b)+1) for _ in range(n+1)]
a=b[0]
dp[1][a]=1
c=max(b)
for i in range(2,n+1):
    a=b[i-1]
    dp[i][a]=max(dp[i][a],1)
    for j in range(max(a-k,0),min(a+k,c+1)):
        if dp[i-1][j]!=0:
            dp[i][a-(a-j)]=max(dp[i-1][a-(a-j)],dp[i-1][j]+1)
    for j in range(c+1):
        dp[i][j]=max(dp[i][j],dp[i-1][j])
print(max(dp[-1]))


### FIXED CODE ###

N,K=map(int,input().split())
class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
ide_ele = 0
b=[int(input()) for _ in range(N)]
c=max(b)
def segfunc(x,y):
    return max(x,y)
seg=SegTree([0]*(c+6),segfunc,ide_ele)
for i in range(N):
    a=b[i]
    seg.update(a,seg.query(max(0,a-K),min(c+2,a+K+1))+1)
print(seg.query(0,c+3))
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0

for i in range(n):
    ans += x // l[i]
    ans %= (10**9 + 7)
print(ans)


### FIXED CODE ###

import fractions
from functools import reduce

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
ans %= (10**9 + 7)
print(ans)
### BUGGY CODE ###

R, G, B, n = map(int, input().split())
ans = 0
r = 0
while r*R <= n:
    g = 0
    while r*R + g*G <= n:
        b = (n - r*R - g*G) // B
        if (r*R + g*G + b*B == n) and (b >= 0):
            ans += 1
        g += 1
    r += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(0, n+1, r):
    for j in range(i, n+1, g):
        if (n-j) % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import re

class Node:
  key = None
  left = None
  right = None
  def __init__(self, k):
    self.key = k

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self, r):
    # 中間巡回順で出力
    if r != None:
      self.inorder(r.left)
      print(" {}".format(r.key), end="")
      self.inorder(r.right)
      

  def preorder(self, r):
    # 先行巡回順で出力
    if r != None:
      print(" {}".format(r.key), end="")
      self.preorder(r.left)
      self.preorder(r.right)

    
n = int(input())
bst = BST()
for _ in range(n):
  query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  if query[0] == 'insert':
    bst.insert(query[1])
  elif query[0] == 'print':
    root = bst.root
    bst.inorder(root)
    print()
    bst.preorder(root)
    print()


### FIXED CODE ###

class Node:
  key = None
  left = None
  right = None
  def __init__(self, k):
    self.key = k

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z

  def inorder(self, r, lis):
    # 中間巡回順で出力
    if r != None:
      self.inorder(r.left, lis)
      lis.append(r.key)
      self.inorder(r.right, lis)


  def preorder(self, r, lis):
    # 先行巡回順で出力
    if r != None:
      lis.append(r.key)
      self.preorder(r.left, lis)
      self.preorder(r.right, lis)

    
n = int(input())
bst = BST()
for _ in range(n):
  # query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  query = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    in_lis = []
    pre_lis = []
    bst.preorder(root, pre_lis)
    bst.inorder(root, in_lis)
    print(" " + " ".join(list(map(str, in_lis))))
    print(" " + " ".join(list(map(str, pre_lis))))
### BUGGY CODE ###

n = int(input())

A = []
for i in range(0, n):
    A.append(int(input()))

cnt = 0
def insertion_sort(L, n, g):
    global cnt
    for i in range(g, n):
        v = L[i]
        j = i - g
        while 0 <= j and v < L[j]:
            L[j+g] = L[j]
            j -= g
            cnt += 1
        L[j+g] = v


def shell_sort(L, n):
    global G
    for i in G:
        insertion_sort(L, n, i)

g = []
for i in range(0, 100):
    x = pow(4, i)
    if n < x:
        break
    else:
        g.append(x)

G = list(reversed(g))
B = A[:]
shell_sort(B, n)

print(len(G))
print(' '.join(str(x) for x in G))
print(cnt)
for i in B:
    print(i)

### FIXED CODE ###

import sys
n = int(input())
A = list(map(int, sys.stdin))

cnt = 0
def insertion_sort(L, n, g):
    global cnt
    for i in range(g, n):
        v = L[i]
        j = i - g
        while 0 <= j and v < L[j]:
            L[j+g] = L[j]
            j -= g
            cnt += 1
        L[j+g] = v


def shell_sort(L, n):
    global G
    for i in G:
        insertion_sort(L, n, i)

G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
shell_sort(A, n)

print(len(G))
print(' '.join(str(x) for x in G))
print(cnt)
for i in A:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

AB = []

for a in A:
    for b in B:
        AB.append(a + b)

AB = sorted(AB, reverse=True)

if 3000 < len(AB):
    AB = AB[:3000]

ABC = []
for ab in AB:
    for c in C:
        ABC.append(ab + c)

ABC = sorted(ABC, reverse=True)

ABC = ABC[:K]
ABC = [str(abc) for abc in ABC]

print("\n".join(ABC))


### FIXED CODE ###

# -*- coding: utf-8 -*-

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

ABC = []

for x in range(X):
    for y in range(Y):
        if (x + 1) * (y + 1) > K:
            break
        for z in range(Z):
            if (x + 1) * (y + 1) * (z + 1) > K:
                break
            ABC.append(A[x] + B[y] + C[z])

ABC = sorted(ABC, reverse=True)

ABC = ABC[:K]
ABC = [str(abc) for abc in ABC]

print("\n".join(ABC))
### BUGGY CODE ###

n, k, q = map(int, input().split())
a  = [int(input()) for i in range(q)]
t = [k]*n
t = [n-1*q for n in t]

for i in range(q):
    for j in range(n):
        if a[i] == j:
            t[j-1] += 1
            break

for i in range(n):
    if t[i] >0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
a  = [int(input()) for i in range(q)]
t = [k]*n
t = [n-1*q for n in t]

for i in range(q):
    t[a[i]-1] +=1

for i in range(n):
    if t[i] >0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

# lr = [list(map(int, input().split())) for _ in range(q)]

# 愚直な計算時間
# ループn回
# リスト切り取りO(n)
# O(n^2)
# 計算リミットが2000msで、n<=10^5
# 0(n)でn=10^6くらいが限度
# O8n^2)だと、n=3000くらい

# 先に回数を数える。累積和的に
hoge = [s[0:(i + 1)].count('AC') for i in range(n)]

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


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

# lr = [list(map(int, input().split())) for _ in range(q)]

# 愚直な計算時間
# ループn回
# リスト切り取りO(n)
# O(n^2)
# 計算リミットが2000msで、n<=10^5
# 0(n)でn=10^6くらいが限度
# O8n^2)だと、n=3000くらい

# 先に回数を数える。累積和的に
# ここで結構時間かかる
# hoge = [s[0:(i + 1)].count('AC') for i in range(n)]

# 修正ver
hoge = [0]
cnt = 0
for i in range(1, n):
    if s[i - 1] + s[i] == 'AC':
        cnt += 1
    hoge.append(cnt)

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

K, S = list(map(int, input().split()))

ans = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        for z in range(0, K+1):
            if x + y + z == S:
                ans += 1
print(ans)


### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        z = S - x - y
        if 0 <= z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

n= int(input())
l=list(map(int,input().split()))
cnt=0
ls = sorted(l)
for i in range(n-1):
    for j in range(i+1,n-1):
        for h in range(j+1,n):
            a,b,c=ls[i],ls[j],ls[h]
            if(a+b<c):
                break
            if(a<b+c)and(b<a+c)and(c<a+b):
                cnt+=1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left

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

l.sort()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    count+=bisect_left(l,l[j]+l[i])-j-1
print(count)
### BUGGY CODE ###

from math import factorial
n = int(input())
a = [int(i) for i in input().split()]
sa = sorted(a,reverse=True)
def comb(n, r):
    b = 1
    for i in range(r):
        b *= n - i
    return b//factorial(r)

sb = sa[1:]
l = len(sb)
n = sa[0]
a1 = sb[l//2 - 1]
a2 = sb[l//2]
k = comb(n,a1)
j = comb(n,a2)
if k > j:
    print(n, a1)
else:
    print(n, a2)

### FIXED CODE ###

from math import factorial
n = int(input())
a = [int(i) for i in input().split()]
sa = sorted(a,reverse=True)
m = sa[0]
sb = sa[1:]
k = [i if m - i > i else m - i for i in sb]
i = k.index(max(k))
print(m, sb[i])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
point = [K for i in range(N)]
A = [int(input()) for j in range(Q)]

for num in A:
    for j in range(1,N+1):
        if not j == num:
            point[j-1] -= 1

for num in point:
    if num > 0:
        print('Yes')
        continue
    print('No')
    

### FIXED CODE ###

N, K, Q = map(int, input().split())
point = [K - Q for i in range(N)]
A = [int(input()) for j in range(Q)]

for num in A:
    point[num-1] += 1

for num in point:
    if num > 0:
        print('Yes')
        continue
    print('No')
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
  ans += i
  
print(ans)

### FIXED CODE ###

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

M=10**9+7
(n,k),*a=[list(map(int,t.split()))for t in open(0)]
r=a if k&1else[[i==j for j in range(n)]for i in range(n)]
d=a
for i in range(1,k.bit_length()):
  p=[]
  for y in d:
    q=[0]*n
    for x,s in zip(y,d):
      for j,t in enumerate(s):
        q[j]+=t*x%M
    p+=q,
  d=p
  if 1<<i&k:
    p=[]
    for y in r:
      q=[0]*n
      for x,s in zip(y,d):
        for j,t in enumerate(s):
          q[j]+=t*x%M
      p+=q,
    r=p
print(sum(t for s in r for t in s)%M)

### FIXED CODE ###

M=10**9+7
(n,k),*a=[list(map(int,t.split()))for t in open(0)]
r=a if k&1else[[i==j for j in range(n)]for i in range(n)]
d=a
for i in range(1,k.bit_length()):
  p=[]
  for y in d:
    q=[0]*n
    for x,s in zip(y,d):
      for j,t in enumerate(s):
        q[j]+=t*x%M
    p+=q,
  d=p
  if 1<<i&k:
    p=[]
    for y in r:
      q=[0]*n
      for x,s in zip(y,d):
        for j,t in enumerate(s):
          q[j]+=t*x%M
      p+=q,
    r=p
print(sum(t for s in r for t in s)%M)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    import bisect
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    #print(a)

    bc=[]
    for i in range(m):
        B = list(map(int, input().split()))
        bc.append(B)
    bc.sort(key=lambda x: x[1])
    #print(bc)

    clis=[]
    for i in range(m)[::-1]:
        clis+=[bc[i][1]]*bc[i][0]
    #print(clis)
    ans=0
    le=len(clis)
    for i in range(n):
        #print(clis[i],a[i])
        if i<le and clis[i]>a[i]:
            ans+=clis[i]
        else:
            ans+=a[i]
        #print(ans)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)
#print(bc)
cnt=0
for i in range(n):
    if bc[cnt][0]>0:
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    else:
        cnt+=1
        if cnt==len(bc):
            break
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    #print(cnt,bc,a)
print(sum(a))
### BUGGY CODE ###

N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = 0
for row in glist:
    s_i = set()
    s_g = set()
    for g in row:
        s_i.add(g)
        s_g.add(p[g])
    out += len(s_i & s_g)
print(out)

### FIXED CODE ###

N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    if len(glist[gx])<len(glist[gy]):
        gx,gy = gy,gx
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = sum([len(set(row) & set(p[g] for g in row)) for row in glist])
print(out)