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

H,W = map(int,input().split())
g = [input() for i in range(H)]
 
c = [[0 for w in range(W)] for h in range(H)]
 
hs = [0 for i in range(W)]
 
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
 
#print(c)
 
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])
 
print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
 
縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''

### FIXED CODE ###

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

c = [[0 for w in range(W)] for h in range(H)]

hs = [0 for i in range(W)]

for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''
### BUGGY CODE ###

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

A = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
    l, r = map(int, input().split())
    A[l][r] += 1
    
for i in range(Q):
    p, q = map(int, input().split())
    cnt = 0
    for i in range(p, q + 1):
        cnt += sum(A[i][p : q + 1])
    print(cnt)

### FIXED CODE ###

n, m, q = map(int, input().split())
A = [[0] * (n+2) for i in range(n+2)]

for i in range(m):
    l, r = map(int, input().split())
    A[l][r] += 1

for i in range(n+1):
    for j in range(n+1):
        A[i][j+1] += A[i][j]
        A[i+1][j] += A[i][j]
        A[i+1][j+1] -= A[i][j]

B = []
for i in range(q):
    p, q = map(int, input().split())
    B.append(A[q][q] - A[q][p-1] - A[p-1][q] + A[p-1][p-1])
    
for b in B:
    print(b)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
L = [K for n in range(N)]

for i in range(Q):
  A = int(input())
  for j in range(N):
    if j != A-1:
      L[j] -= 1
      
for j in range(N):
  if L[j] > 0:
    print("Yes")
  else: 
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
L = [0 for n in range(N)]

for i in range(Q):
  A = int(input())
  L[A-1] += 1

for j in range(N):
  if K - (Q-L[j]) > 0:
    print("Yes")
  else: 
    print("No")
### BUGGY CODE ###

N = int(input())


def query(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


"""
初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
まずis_okを定義すべし
ng, okは,とり得る最小の値-1,とり得る最大の値+1
"""

# 適当にいじる
ng = -1  # ind=0が条件を満たすこともあるため
ok = N  # ind=len(a)-1が条件を満たさないこともあるため

# いじらない
# okとngのどちらが大きいかわからないことを考慮
while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid




### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

import numpy as np

def warshall_floyd(V, d):
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i, k] + d[k, j]
                if d[i, j] > dk:
                    d[i, j] = dk
                    d[j, i] = dk
    return d

INF = 10 ** 9
n, m, l = map(int, input().split())
E = INF * np.ones([n + 1, n + 1], np.int)
for _ in range(m):
    i, j, c = map(int, input().split())
    E[i, j] = c
    E[j, i] = c

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

d = warshall_floyd(n, E)
E2 = (d <= l).astype(np.int)
E2[E2 == 0] = INF
d2 = warshall_floyd(n, E2)

for i in range(q):
    s, t = Q[i]
    di = d2[s, t]
    if di >= INF:
        print(-1)
    else:
        print(di - 1)


### FIXED CODE ###

INF = 10 ** 9
n, m, l = map(int, input().split())
d = [[INF for j in range(n + 1)] for i in range(n + 1)]
d2 = [[INF for j in range(n + 1)] for i in range(n + 1)]
for _ in range(m):
    i, j, c = map(int, input().split())
    d[i][j] = c
    d[j][i] = c
    if c <= l:
        d2[i][j] = 1
        d2[j][i] = 1

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

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
                if dk <= l:
                    d2[i][j] = 1
                    d2[j][i] = 1

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d2[i][k] + d2[k][j]
            if d2[i][j] > dk:
                d2[i][j] = dk
                d2[j][i] = dk

for i in range(q):
    s, t = Q[i]
    di = d2[s][t]
    if di >= INF:
        print(-1)
    else:
        print(di - 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp = [[[0] * (80 * 80 * 2 + 1) for _ in range(W)] for _ in range(H)]
dp[0][0][X[0][0]] = 1
for i in range(H):
  for j in range(W):
    for k in range(80 * 3 + 1):
      if dp[i][j][k] == 0: continue
      if i + 1 < H:
        u = k + X[i + 1][j]
        v = abs(k - X[i + 1][j])
        dp[i + 1][j][u] += dp[i][j][k]
        dp[i + 1][j][v] += dp[i][j][k]
      if j + 1 < W:
        u = k + X[i][j + 1]
        v = abs(k - X[i][j + 1])
        dp[i][j + 1][u] += dp[i][j][k]
        dp[i][j + 1][v] += dp[i][j][k]
res = 80
#print(dp[1][1])
for k in range(81):
  if dp[-1][-1][k]: res = min(k, res)
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
dplimit = [[0] * W for _ in range(H)]
dplimit[-1][-1] = 80
for i in range(H - 1, -1, -1):
  for j in range(W - 1, -1, -1):
    x = X[i][j]
    if i > 0: dplimit[i - 1][j] = max(dplimit[i - 1][j], dplimit[i][j] + x)
    if j > 0: dplimit[i][j - 1] = max(dplimit[i][j - 1], dplimit[i][j] + x)
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp2[j].add(u)
          if v <= dplimit[i][j]: dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp1[j + 1].add(u)
          if v <= dplimit[i][j]: dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp1[j].add(u)
          if v <= dplimit[i][j]: dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp2[j + 1].add(u)
          if v <= dplimit[i][j]: dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)
### BUGGY CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    c = 0
    key = 0
    while c < n:
        sc = list(set(str(key+1)))
        if sc.count("4") or sc.count("6"):
            key += 1
        else:
            c += 1
            key += 1
    print key

### FIXED CODE ###

ref = ["0","1","2","3","5","7","8","9"]
while True:
    n = int(raw_input())
    if n == 0: break
    ans = ""
    for i in str(oct(n))[1:]:
        ans += ref[int(i)]
    print ans
### BUGGY CODE ###

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  ans=0
  C=[]
  for i in D:
    ans+=i
    C.append(ans)
  return C


for i in range(K):
  D=f(A)
  A=D
  if A==[N]*(N+1):
    break
print(*A[:-1])

### FIXED CODE ###

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)
### BUGGY CODE ###

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

def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            d = make_divisors(i)
            d.pop()
            leng = len(set(d)-set(cf[1:]))
            if len(d) == leng:
                cf.append(i)
    return cf

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

c = cf(A, B)
ans =len(c)
print(ans)


### FIXED CODE ###

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

def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def prime_factor(n):  # nを素因数分解
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

g = gcd(A, B)
f = prime_factor(g)

ans = len(f)
if f[0][0] != 1:
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import Counter

S = input()
S2 = S + S
T = input()
SC = Counter(S)
TC = Counter(T)

N = len(S)
ans = 0
now = 0

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

for t in T:
    i = S2[now: now + N].find(t)
    ans += i + 1
    now += i + 1
    now %= N

print(ans)

### FIXED CODE ###

from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

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

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    now = At[x]
    if now + 1 >= N:
        ans += 1
    now += 1
    now %= N

print(ans * N + now)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

for i in range(m):
    x_in, y_in = map(int, input().split())
    x.append(x_in)
    y.append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                ret = max(tmp, ret)
        memo[i] = ret
        return ret
    else:
        return memo[i]


for i in x[1:]:
    tmp = dp(i)
    ans = max(tmp, ans)

print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    y[x_in].append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in in y[i][1:]:
            tmp = dp(x_in) + 1
            if tmp > ret:
                ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))
### BUGGY CODE ###

if __name__ == '__main__':
    x = int(input())
    ans = x+2
    for i in range(x, 0, -1):
        if x % i == 0:
            q = (int(x/i) - 1) + (i-1)
            if q < ans:
                ans = q
            else:
                print((int(x/i) - 1) + (i-1))
                break

### FIXED CODE ###

n = int(input())
s = int(n ** 0.5)
list = []
for i in range(1, s + 1):
    if n % i == 0:
        list.append(int(i + n / i - 2))
print(min(list))
### BUGGY CODE ###

"""
解説を参考に作成
"""


def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    for _ in range(M):
        B, C = map(int, input().split())
        A += [C] * B
    A.sort(reverse=True)
    print(sum(A[:N]))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説を参考に作成 その3
"""


def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    CB = [list(reversed([int(i) for i in input().split()])) for _ in range(M)]
    CB = list(sorted(CB, reverse=True))

    count = 0
    flag = False
    for cb in CB:
        for b in range(cb[1]):
            if A[count] < cb[0]:
                A[count] = cb[0]
            else:
                flag = True
                break
            count += 1
            if count >= N:
                flag = True
                break

        if flag:
            break
    print(sum(A))


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

import sys
from sys import stdin
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

readline = stdin.readline

def inp():
    return int(readline())
def inpl():
    return list(map(int, readline().split()))

INF = 1001001001

# ---------------------------------------

def main():
    n, k = inpl()
    p = [0] + inpl()
    c = [0] + inpl()

    ans = - INF

    for i in range(1, n + 1):
        cycle_cnt = 0
        cycle_sum = 0
        v = i

        while True:
            v = p[v]
            cycle_cnt += 1
            cycle_sum += c[v]
            if v == i: break
        
        cnt = 0
        path = 0

        while True:
            v = p[v]
            cnt += 1
            path += c[v]

            if cnt > k: break

            num = (k - cnt) // cycle_cnt
            score = path + max(0, cycle_sum) * num
            ans = max(ans, score)

            if v == i: break

    print(ans)

main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

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

INF = 1001001001

# ---------------------------------------



n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

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

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

ans = 0
for i in range(a,b+1):
  if i % x==0 :ans += 1
    
print(ans)


### FIXED CODE ###

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


ans = b//x - (a-1)//x
print(ans)
### BUGGY CODE ###

N=int(input())
ans=0
yakusu=[0]*(10**7+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        yakusu[j]+=1
for i in range(len(yakusu)):
    ans+=(i)*yakusu[i]
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
yakusu=[0]*(10**7+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        yakusu[j]+=1
for i in range(len(yakusu)):
    ans+=(i)*yakusu[i]
print(ans)
### BUGGY CODE ###

s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt) % DIV
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt) % DIV
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % (10**9 + 7))

### FIXED CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])
### BUGGY CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.deepcopy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :
    
    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])

### FIXED CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.copy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :

    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])

### FIXED CODE ###

N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])
### BUGGY CODE ###

#https://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
    ans1=d[-1]
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
    ans2=d[-1]
    if ans1>ans2:
      return ['inf']
    else:
      return [-ans1]
n,m,p=map(int,input().split())
g=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  g.append([a,b,-(c-p)])
g.append([n,n+1,0])
ans=BF(g,n+1,1)[-1]
if ans=='inf':
  print(-1)
else:
  print(max(ans,0))

### FIXED CODE ###

#https://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
    ans1=d[-1]
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
    ans2=d[-1]
    if ans1>ans2:
      return ['inf']
    else:
      return [-ans1]
n,m,p=map(int,input().split())
g=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  g.append([a,b,-(c-p)])
g.append([n,n+1,0])
ans=BF(g,n+1,1)[-1]
if ans=='inf':
  print(-1)
else:
  print(max(ans,0))
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
BC=list(list(map(int,input().split())) for  _ in range(M))
BC.sort(key=lambda x: x[1],reverse=True)

for b,c in BC:
    if c>A[b-1]:
        A=[c]*b+A[b:]
        A.sort()
    elif c>min(A):
        for i in range(b):
            if A[i]<c:
                A[i]=c
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))