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

import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

X.sort(key=lambda x: x[0])

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while 1:
        u, f, x = X[j]
        if u > 2*q:
            break
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[-1 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
ptr = 0
for r in range(1,n+1):
  while ptr < m and lrx[ptr][1] < r:
    ptr += 1
  for g in range(r):
    for b in range(max(1,g)):
      for x,y,z in permutations((r,g,b)):
        dp[x][y][z] = 0
  while ptr < m and lrx[ptr][1] == r:
    l,_,t = lrx[ptr]
    if t != 1:
      for g in range(l):
        for b in range(max(1,g)):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 2:
      for g in range(l,r):
        for b in range(l):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 3:
      for g in range(l,r):
        for b in range(l,g):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    ptr += 1
for r in range(n):
  for g in range(n):
    for b in range(n):
      mx = max(r,g,b)
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[mx+1][g][b] >= 0:
        dp[mx+1][g][b] += v
        dp[mx+1][g][b] %= mod
      if dp[r][mx+1][b] >= 0:
        dp[r][mx+1][b] += v
        dp[r][mx+1][b] %= mod
      if dp[r][g][mx+1] >= 0:
        dp[r][g][mx+1] += v
        dp[r][g][mx+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    for x,y,z in permutations((n,i,j)):
      if dp[x][y][z] >= 0:
        ans += dp[x][y][z]
        ans %= mod
print(ans)

### FIXED CODE ###

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)
### BUGGY CODE ###

import math

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

ans = 0
for x in range(1, N+1, 1):
  i = math.floor(A * x / B) - (A * math.floor(x / B))
  if i > ans:
    ans = i
else:
  print(ans)

### FIXED CODE ###

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

def fl(i):
  return ((A * i) // B) - (A * (i // B))

if B <= N:
  print(int(fl(B - 1)))
else:
  print(int(fl(N)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
high = 0
for i in range(N-K+1):
    tmp = 0
    for p in P[i:i+K]:
        tmp += p
    if tmp > high:
        high = tmp
        e = i
exp = 0
for p in P[e:e+K]:
    exp += sum(range(1,p+1)) / p

print(exp)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
tmp = sum(P[:K])
high = tmp
e = 0
for i in range(1, N-K+1):
    tmp -= P[i-1]
    tmp += P[i+K-1]
    if tmp > high:
        high = tmp
        e = i
exp = 0
for p in P[e:e+K]:
    exp += sum(range(1,p+1)) / p

print(exp)
### BUGGY CODE ###

import sys
from copy import deepcopy

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def drop(H, G):
    G = [[n for n in col if n != -1] for col in zip(*G)]
    G = [[-1] * (H - len(col)) + col for col in G]
    G = [list(row) for row in zip(*G)]
    return G


def main():
    H, W, K = map(int, readline().split())
    G_init = [list(map(int, list(readline().strip()))) for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            G = deepcopy(G_init)
            G[i][j] = -1
            G = drop(H, G)

            current_ans = 0
            step = 0
            while True:
                score = 0
                for row in G:
                    seq = [[row[0], 1]]
                    for n in row[1:]:
                        if n == seq[-1][0]:
                            seq[-1][1] += 1
                        else:
                            seq.append([n, 1])
                    idx = 0
                    for n, c in seq:
                        if n != -1 and c >= K:
                            score += n * c
                            row[idx : idx + c] = [-1] * c
                        idx += c

                if score == 0:
                    break

                current_ans += score * pow(2, step)
                step += 1
                G = drop(H, G)

            if current_ans > ans:
                ans = current_ans

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from copy import deepcopy

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def drop(H, G):
    G = [[n for n in col if n != -1] for col in zip(*G)]
    G = [[-1] * (H - len(col)) + col for col in G]
    G = [list(row) for row in zip(*G)]
    return G


def main():
    H, W, K = map(int, readline().split())
    G_init = [list(map(int, list(readline().strip()))) for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            G = deepcopy(G_init)
            G[i][j] = -1
            G = drop(H, G)

            current_ans = 0
            step = 0
            while True:
                score = 0
                for row in G:
                    seq = [[row[0], 1]]
                    for n in row[1:]:
                        if n == seq[-1][0]:
                            seq[-1][1] += 1
                        else:
                            seq.append([n, 1])
                    idx = 0
                    for n, c in seq:
                        if n != -1 and c >= K:
                            score += n * c
                            row[idx : idx + c] = [-1] * c
                        idx += c

                if score == 0:
                    break

                current_ans += score * pow(2, step)
                step += 1
                G = drop(H, G)

            if current_ans > ans:
                ans = current_ans

    print(ans)
    return


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

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

ans=[0 for i in range(N)]
ans[1]=abs(h[1]-h[0])


for i in range(2,N):
    ans[i] = min(abs(h[i] - h[j]) + ans[j] for j in range(max(0,i-K),i))
print(ans[N-1])

### FIXED CODE ###

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

    ans=[0]*N
    ans[1]=abs(h[1]-h[0])


    for i in range(2,N):
        ans[i] = min(abs(h[i] - h[j]) + ans[j] for j in range(max(0,i-K),i))
    print(ans[N-1])
    
main()
### BUGGY CODE ###


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

mod = 10**9+7
ans = 0

for i in range(60):
  one=0
  for a in  A:
    one += a>>i&1
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import numpy as np
mod = 10**9+7
ans = 0
A = np.array(A)
for i in range(60):
  one = np.count_nonzero(A>>i&1)
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

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

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

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = (n*pow(2, n, MOD) - n) % MOD
for i in range(n):
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)


### FIXED CODE ###

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

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    dp = [INF]*N
    dp[0] = 0
    keys = [0]
    while heap:
        l, r, c = heappop(heap)
        
        s = INF
        for k in keys:
            if k < l or k >= r:
                continue
            s = min(s, dp[k])
        dp[r] = min(dp[r], s+c)
        keys.append(r)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while len(heap) > 0:
        cost, node = heappop(heap)
        if node == t:
            return cost

        if node in visited:
            continue

        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 in visited:
                continue

            heappush(heap, (cost + cost2, node2))

    return -1

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    links = [[] for _ in range(N)]
    for i in range(1, N):
        links[i].append((0, i-1))

    for _ in range(M):
        l, r, c = map(int, input().split())
        links[l-1].append((c, r-1))
    
    return dijkstra(0, N-1, links)
    

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

input();l=input().split();x=1
for j in sorted(l):x*=int(j);
if x>1e18:x=-1
print(x)

### FIXED CODE ###

i = input
i()
x = 1
l = i().split()
if '0' in l:
    print(0)
    quit()
for j in l:
    x *= int(j)
    if x > 1e18:
        print(-1)
        quit()
print(x)
### BUGGY CODE ###

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

for j in range(n):
    for k in range(j+1,n):
        if sorted(list(s[j]))==sorted(list(s[k])):
                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
d={}
ans=0
for i in range(n):
    s=list(input())
    s.sort()
    l=''.join(s)
    if l in d:
        ans+=d[l]
        d[l]+=1
    else:
        d[l]=1
print(ans)
### BUGGY CODE ###

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

nums = []
for _ in range(n):
  a, b = map(int, input().split())
  nums.extend([a]*b)
  
sn = sorted(nums)
print(sn[k-1])


### FIXED CODE ###

from operator import itemgetter
n, k = map(int, input().split())

arr = []
k_sum = 0
for i in range(n):
  a, b = map(int, input().split())
  d = {}
  d['num'] = a
  d['count'] = b
  arr.append(d)
  
arr = sorted(arr, key=itemgetter('num'))

for i in range(n):
  k_sum += arr[i]['count']
  if k <= k_sum:
    print(arr[i]['num'])
    exit(0)
### BUGGY CODE ###

x= int(input())
k = 1
while True:
  if k*x == 360:
    print(k)
    break
  k+=1

### FIXED CODE ###

x= int(input())
k = 1
while True:
  a = x*k
  if a%360==0:
    print(k)
    break
  k+=1
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    value[a]+=b
def dfs(node,p,score):
    temp = []
    for v in nodes[node]:
        if v !=p:
            value[v]+=score
            dfs(v,node,value[v])
dfs(1,-1,value[1])
print(*value[1:])



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    value[a]+=b
def dfs(node,p,score):
    for v in nodes[node]:
        if v !=p:
            value[v]+=score
            dfs(v,node,value[v])

dfs(1,-1,value[1])
for i in range(1,n+1):
    sys.stdout.write('{} '.format(int(value[i])))
### BUGGY CODE ###

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

L.sort()
ans=0
for i in range(n-1):
  for j in range(i+1,n-1):
    tmp=sorted(L[j+1:],reverse=True)
    for k in range(len(tmp)):
      if L[i]+L[j]>tmp[k]:
        ans+=len(tmp)-k
        break
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
L=list(map(int,input().split()))

L.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    index=bisect.bisect_left(L,L[i]+L[j])
    ans+=index-(j+1)
    
print(ans)
### BUGGY CODE ###

# D - We Love ABC

S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a += pat
    elif s == 'B':
        ab += a
    elif s == 'C':
        abc += ab
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a += 2*a + pat
        ab += 2*ab + tmpa
        abc += 2*abc + tmpab
        pat *= 3

print(abc%MOD)

### FIXED CODE ###

# D - We Love ABC
import sys
readline = sys.stdin.readline

S = list(str(readline().rstrip()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)
### BUGGY CODE ###

import numpy as np

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

for i in range(n):
  cnt = a.count(i+1)
  if k - q + cnt > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np

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

score = [k - q]*(n+1)

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

for i in range(1,n+1):
  if score[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from fractions import gcd

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

lcm = N*M//gcd(N, M)

ans = lcm

for n in range(N):
    for m in range(M):
        if (lcm//N)*n  == (lcm//M)*m:
            if S[n] != T[m]:
                ans = -1
                break
                
print(ans)


### FIXED CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=list(input())
T=list(input())
L=gcd(N,M)
print(N*M//L if all([S[i*N//L]==T[i*M//L] for i in range(L)]) else "-1")
### BUGGY CODE ###

try:
	while True:
		ans = [2]
		limit = input()
		for n in range(3, limit + 1, 2):
			i = 1
			while True:
				if n % ans[i-1] == 0:
					break
				else:
					if(i == len(ans)):
						ans.append(n)
					i = i + 1
		print len(ans)
except EOFError:
	pass

### FIXED CODE ###

def prime_count(n):
	j = 0
	ans = [1] * (n + 1)
	ans[0] = ans[1] = 0
	for i in xrange(3, n + 1, 2):
		if i * 2 > n:
			break
		if ans[i] != 0:
			for j in xrange(2 * i, n + 1, i):
				ans[j] = 0
	for k in xrange(2 * 2, n + 1, 2):
		ans[k] = 0
	print sum(ans)

try:
	while True:
		n = input()
		prime_count(n)
except EOFError:
	pass
### BUGGY CODE ###

nb=int(input())
liste = [int(x) for x in input().split()]
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste.count(n)
  for loop in range(roger):
    liste.append(r)
  diff = r-n
  somme += diff * roger
  print(somme)

### FIXED CODE ###

nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*((10**5)+1)
for loop in range(len(liste)):
  liste2[liste[loop]] +=1
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)
### BUGGY CODE ###

from operator import itemgetter

n, m = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()])
#print(a)

bc = []
for _ in range(m):
  bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=itemgetter(1), reverse=True)
#print(bc)

for b,c in bc:
  if a[0] > c:
    break
  for _ in range(b):
    if a[0] < c:
      del a[0]
      a.append(c)
    else:
      break
      
ans = sum(a)

print(ans)
    

### FIXED CODE ###

from operator import itemgetter

n, m = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()])
#print(a)

bc = []
for _ in range(m):
  bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=itemgetter(1), reverse=True)
#print(bc)

change = []
for b,c in bc:
  len_change = len(change)
  b_up = b
  if n - len_change < b:
    b_up = n - len_change
  #print(b_up)
  change += [c]*b_up
  if b_up != b:
    break
change += [0]*(n-len(change))

ans = 0
for i in range(n):
  #print(ans)
  #print(i)
  if a[i] < change[i]:
    ans += change[i]
  else:
    ans += sum(a[i:])
    break
    
print(ans)
### BUGGY CODE ###

n = int(input())
bro = [x for x in range(1, n+1)]
number = 3
while number <= n:
  try:
    bro.remove(number)
  except ValueError:
    pass
  number += 3
number = 5
while number <= n:
  try:
    bro.remove(number)
  except ValueError:
    pass
  number += 5
print(sum(bro))

### FIXED CODE ###

n = int(input())
sumi = 0
for i in range(1, n+1):
    if i % 3 != 0 and i % 5 != 0:
        sumi += i
print(sumi)