CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 110101以下の数は、以下のいずれかである
#
# 110101
# 110100 (1を一つ選んで0にする、それ以下の桁はなんでもよいので?とする)
# 1100?? 
# 10????
# 0?????
#
# 上の各パターンについて条件を満たすものをそれぞれ探し、maxをとる
# 各パターンでは、0になるべき桁が必ず0になるようにする
#
# 実装上は、?をすべて1で置換。orをとっても以下の数値を超えないようにする
#
# 110101
# 110011
# 101111
# 011111
#


import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

N, K = list(map(int, input().split()))
A = []
B = []
for n in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

ret = 0

# orをとって 110101 以下になるもののみretに足す
for n in range(N):
    if K | A[n] == K:
        ret += B[n]

# Kの下位ビットから順に見ていき、もし1があれば、その桁を0にして、その桁より下位をすべて1にする
for n in range(31):
    # n番目の桁が0なら、1にする
    if (K >> n) & 1 == 0:
        K |= (1 << n)
    else:
        # n番目の桁が1なら、0にする
        K ^= (1 << n)

        local_ret = 0
        for m in range(N):
            if K | A[m] == K:
                local_ret += B[m]
        ret = max(ret, local_ret)

        # また1に戻す
        K |= (1 << n)


print(ret)

    



# Optimized solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 動画解説を見る
#
# 110101以下の数は、以下のいずれかである
#
# 110101
# 110100 (1を一つ選んで0にする、それ以下の桁はなんでもよいので?とする)
# 1100??
# 10????
# 0?????
#
# 上の各パターンについて条件を満たすものをそれぞれ探し、maxをとる
# 各パターンでは、0になるべき桁が必ず0になるようにする
#
# 実装上は、?をすべて1で置換。orをとった結果、0の箇所に1が来ないようにする
#
# 110101
# 110011
# 101111
# 011111



import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import re
import string

N, K = list(map(int, input().split()))
A = []
B = []
for n in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

ret = 0

# orをとって 110101 以下になるもののみretに足す
for n in range(N):
    if K | A[n] == K:
        ret += B[n]

# Kの下位ビットから順に見ていき、もし1があれば、その桁を0にして、その桁より下位をすべて1にする
for i in range(31):
    # n番目の桁が0なら、1にする
    if (K >> i) & 1 == 0:
        K |= (1 << i)
    else:
        # n番目の桁が1なら、0にする
        K ^= (1 << i)

        local_ret = 0
        for n in range(N):
            if K | A[n] == K:
                local_ret += B[n]
        ret = max(ret, local_ret)

        # また1に戻す
        K |= (1 << i)


print(ret)
# Original solution
n, k = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(n)]

# そのままの　ｋ
ans = 0
for a, b in ab:
    if k & a == a:
        ans += b

for i in range(31):
    # 上からi桁目までいっち、あとは1111
    if k >> i & 1 == 0:
        continue
    nk = k
    nk &= ~(1 << i)
    for j in range(i - 1, -1, -1):
        nk |= 1 << j

    cnt = 0
    for j in range(n):
        a, b = ab[j]
        if (a & nk) == a:
            cnt += b
    ans = max(ans, cnt)
print(ans)


# Optimized solution
n, k = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(n)]

ans = sum([b for a, b in ab if k & a == a])

for i in range(30):
    if k >> i & 1:
        nk = 1 << i ^ k
        for j in range(i):
            nk |= 1 << j
        ans = max(ans, sum([b for a, b in ab if nk & a == a]))
print(ans)
# Original solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
int_list = []
for _ in range(N):
    A, B = list(map(int, input().split()))
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
int_list = []
for _ in range(N):
    A, B = list(map(int, input().split()))
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
                break
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)
# Original solution
# Problem A

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

tmp = B
B = A
A = tmp
tmp = A
A = C
C = tmp

# output
print(("%d %d %d"%(A, B, C)))


# Optimized solution
# Problem A - ABC Swap

# input
X, Y, Z = list(map(int, input().split()))

# swap
tmp = X
X = Y
Y = tmp
tmp = X
X = Z
Z = tmp

# output
print(("%d %d %d"%(X, Y, Z)))
# Original solution
a,b,c = input().split()
print((c+' '+a+' '+b)) 

# Optimized solution
a,b,c=map(int,input().split())
print(c,a,b,sep=' ')
# Original solution
# [箱A, 箱B, 箱C]
list = input().split()

# 箱Aと箱B入れ替え
temp = list[0]
list[0] = list[1]
list[1] = temp

# 箱Aと箱C入れ替え
temp = list[0]
list[0] = list[2]
list[2] = temp              
              
print((' '.join(list)))

# Optimized solution
# [箱A, 箱B, 箱C]
list = input().split()
 
# 箱Aと箱B入れ替え
list[0], list[1] = list[1], list[0]
 
# 箱Aと箱C入れ替え
list[0], list[2] = list[2], list[0]    
              
print((' '.join(list)))
# Original solution
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

n, m = list(map(int, input().split()))
a = list([int(x) - 1 for x in input().split()])

bit0 = BIT(m)
bit1 = BIT(m)
for i in range(n-1):
    x, y = a[i], a[i+1]
    bit1.add(0, (y - x) % m)
    if (y - x) % m < 2:
        continue
    x = (x + 2) % m
    if x <= y:
        bit0.add(x, -1)
        bit1.add(x, x - 1)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, -(x - 1))
    else:
        bit0.add(x, -1)
        bit1.add(x, x - 1)

        b = (0 - (x - 1)) % m
        bit0.add(0, -1)
        bit1.add(0, -b)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, b)

ans = min(bit0.sum(i) * i + bit1.sum(i) for i in range(m))
print(ans)


# Optimized solution
from itertools import accumulate
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list([int(x) - 1 for x in input().split()])

cnt0 = [0] * m
cnt1 = [0] * m
for i in range(n-1):
    cnt0[a[i+1]] += (a[i+1] - a[i]) % m - 1
    if (a[i] + 1) % m <= a[i+1]:
        cnt1[(a[i]+1) % m] += 1
        cnt1[a[i+1]] -= 1
    else:
        cnt1[(a[i]+1) % m] += 1
        cnt1[0] += 1
        cnt1[a[i+1]] -= 1
cnt1 = list(accumulate(cnt1))
ans = float('inf')
tmp = 0
for i in range(n-1):
    tmp += min((a[i+1] - a[i]) % m, a[i+1] + 1)
ans = tmp
for i in range(m-1):
    tmp += cnt0[i] - cnt1[i]
    ans = min(ans, tmp)
print(ans)
# Original solution
n,m,*A=list(map(int,open(0).read().split()));l=3*m;D=[0]*l;S=0
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(1,l):D[i]+=D[i-1]\n"*2);print((S-max(D[a]+D[a+m]for a in A)))

# Optimized solution
_,m,*A=list(map(int,open(0).read().split()));S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print((S-l-max(D[a]+D[a+m]for a in A)))
# Original solution
_,m,*A=list(map(int,open(0).read().split()));S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec(("i=0;"+"D[i]+=D[i-1];i+=1;"*l)*2);print((S-l-max(D[a]+D[a+m]for a in A)))

# Optimized solution
_,m,*A=list(map(int,open(0).read().split()));S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):b+=m*(b<a);k=b-a;S+=k;D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print((S-l-max(D[a]+D[a+m]for a in A)))
# Original solution
from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

bit = Bit(m + 1)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    bit.add(a + 1, 1)
    bit.add(b, -1)
    if a > b:
        bit.add(1, 1)
        ans_1 += b
    else:
        ans_1 += b - a

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= bit.sum(px)
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


# Optimized solution
from collections import defaultdict
from itertools import accumulate

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= cum[px]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)
# Original solution
from collections import defaultdict
from itertools import accumulate

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= cum[px]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


# Optimized solution
from collections import defaultdict
from itertools import accumulate

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(1, m):
    ans_x = ans_prev
    if x in counter:
        ans_x += sum((x - a) % m - 1 for a in counter[x])
    ans_x -= cum[x]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

ex = [0] * m
left = [0] * (2*m)
right = [[0,0] for _ in range(2*m)]

ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    ans += (a1-a0)%m
    left[a0+1] += 1
    right[a1 + (a0>a1)*m][0] += 1
    right[a1 + (a0>a1)*m][1] += (a1-a0)%m -1

now = left[0]
dif = 0
for i in range(1,2*m):
    dif += now
    ex[i%m] -= dif
    now += left[i] - right[i][0]
    dif -= right[i][1]

ans += min(ex)
print(ans)

# Optimized solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

imos = [0] * (2*m+2)
ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    dif = (a1-a0)%m
    ans += dif
    if(dif>=2):
        imos[a0+2] += 1
        imos[a0+dif+1] -= dif
        imos[a0+dif+2] += dif-1

# print(imos)

for i in range(1,2*m+2):
    imos[i] += imos[i-1]
# print(imos)

for i in range(1,2*m+2):
    imos[i] += imos[i-1]
# print(imos)

for i in range(m):
    imos[i] += imos[i+m]

ans -= max(imos[:m])
print(ans)
# Original solution
def main():
    n, m = list(map(int, input().split()))
    a = list([int(x)-1 for x in input().split()])
    event = [[] for _ in [0]*m]
    for j, i in enumerate(a):
        if j < n-1:
            A = m-a[j+1]
            if A < m:
                event[A].append((True, j))
        B = m-i
        if B < m:
            event[B].append((False, j))
    leader = 1
    now = a[-1]
    for i in range(n-1):
        if a[i] > a[i+1]:
            leader += 1
            now += a[i]
    s = a[0]
    ans = 10**20
    for i in range(m):
        b = list([(x+i) % m for x in a])
        for e, j in event[i]:
            if e:
                leader += 1
                now += ((a[j]+i) % m)
            else:
                now -= m
                if j != n-1:
                    leader -= 1
        now += leader
        ans = min(ans, now-1-(s+i) % m)
    print(ans)


main()


# Optimized solution
def main():
    n, m = list(map(int, input().split()))
    a = list([int(x)-1 for x in input().split()])
    event = [[] for _ in [0]*m]
    for j, i in enumerate(a):
        if j < n-1:
            A = m-a[j+1]
            if A < m:
                event[A].append((True, j))
        B = m-i
        if B < m:
            event[B].append((False, j))
    leader = 1
    now = a[-1]
    for i in range(n-1):
        if a[i] > a[i+1]:
            leader += 1
            now += a[i]
    s = a[0]
    ans = 10**20
    for i in range(m):
        for e, j in event[i]:
            if e:
                leader += 1
                now += ((a[j]+i) % m)
            else:
                now -= m
                if j != n-1:
                    leader -= 1
        now += leader
        ans = min(ans, now-1-(s+i) % m)
    print(ans)


main()
# Original solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

#C
def C():
    n,m = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    b = [0]*(m+10)
    ans = 0
    f = [0]*(m+10)
    for i in range(n-1):
        r = (a[i+1]-a[i])%m
        ans += r
        if r < 2:
            continue
        if a[i+1] >= (a[i]+2)%m:
            f[(a[i]+2)%m] += 1
            b[(a[i]+2)%m] += 1
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
        else:
            b[0] += 1
            f[0] += (-a[i]-1)%m
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
            b[a[i]+2] += 1
            f[a[i]+2] += 1
            b[m] -= 1
    for i in range(m-1):
        b[i+1] += b[i]
    for i in range(m-1):
        f[i+1] += f[i]+b[i]
    print((ans-max(f)))
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    a = LI()
    ans = sum([(a[i+1]-a[i])%m for i in range(n-1)])
    s = [0]*(2*m)
    f = [0]*(2*m)
    x = a[0]-1
    for i in range(1,n):
        y = a[i]-1
        if y < x:
            y += m
        if x+1 >= y:
            x = a[i]-1
            continue
        s[x+2] += 1
        s[y+1] -= 1
        f[y+1] -= y-x-1
        x = a[i]-1
    for i in range(2*m-1):
        s[i+1] += s[i]
        f[i+1] += f[i]+s[i+1]
    f = [f[i]+f[i+m] for i in range(m)]
    print((ans-max(f)))
    return

#Solve
if __name__ == "__main__":
    solve()
# Original solution
def is_ok(A, index, key):
    return A[index] >= key


def binary_search(A, key):
    ng = -1
    ok = len(A)

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(A, mid, key):
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()
    for m in range(M):
        B, C = list(map(int, input().split()))
        idx = binary_search(A, C)
        A[idx:idx] = [C] * B
        A = A[B:]

    print((sum(A)))

main()


# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    h = {}
    for a in A:
        if a in h:
            h[a] += 1
        else:
            h[a] = 1
    for m in range(M):
        B, C = list(map(int, input().split()))
        if C in h:
            h[C] += B
        else:
            h[C] = B
    nums = list(h.keys())
    nums.sort(reverse=True)
    c = 0
    s = 0
    for i in nums:
        if c + h[i] >= N:
            s += i * (N - c)
            break
        else:
            c += h[i]
            s += i * h[i]
    print(s)

main()
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = list(list(map(int,input().split())) for i in range(m))

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])
t = 0
for i in range(m):
    for j in range(bc[i][0]):
        if t != n:
            if a[t] < bc[i][1]:
                a[t] = bc[i][1]
                t+=1
            else:
                break
    else:
        continue
    break

print((sum(a)))


# Optimized solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = list(list(map(int,input().split())) for i in range(m))

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])
t = 0
for i in range(m):
    for j in range(bc[i][0]):
        if t != n:
            if a[t] < bc[i][1]:
                a[t] = bc[i][1]
                t+=1
            else:
                break
        else:
            break
    else:
        continue
    break

print((sum(a)))
# Original solution
n, m = list(map(int, input().split()))
list_score = list(map(int, input().split()))
list_kard = [ list(map(int,input().split(" "))) for i in range(m)]

for i in range(m):
    k = list_kard[i]
    l = [k[1]]*k[0]
    list_score.extend(l)

list_score.sort(reverse=True)
print((sum(list_score[:n])))

# Optimized solution
n, m = list(map(int, input().split()))
list_score = list(map(int, input().split()))
list_kard = [ list(map(int,input().split(" "))) for i in range(m)]

list_score_colume = list(set(list_score))

for i in range(len(list_score_colume)):
    k = [list_score.count(list_score_colume[i]), list_score_colume[i]]
    list_kard.append(k)


list_kard = sorted(list_kard, key=lambda x: x[1], reverse=True)


ans = 0
cnt = 0
for i in range(len(list_kard)):
    k = list_kard[i]
    if cnt + k[0] <= n:
        ans += k[0]*k[1]
        cnt += k[0]
    else:
        ans += k[1]*(n-cnt)
        break

print(ans)
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(m):
    b, c = list(map(int, input().split()))
    a += [c] * b

a.sort(reverse=True)
print((sum(a[:n])))

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a_min = min(a)
for i in range(m):
    b, c = list(map(int, input().split()))
    if c > a_min:
        a += [c] * b

a.sort(reverse=True)
print((sum(a[:n])))
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a_min = min(a)
for i in range(m):
    b, c = list(map(int, input().split()))
    if c > a_min:
        a += [c] * b
        if b > n//2:
            a = sorted(a, reverse=True)[:n]

a.sort(reverse=True)
print((sum(a[:n])))

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a_min = min(a)
for i in range(m):
    b, c = list(map(int, input().split()))
    if c > a_min:
        a += [c] * b
        a = sorted(a, reverse=True)[:n]
        a_min = a[-1]

a.sort(reverse=True)
print((sum(a[:n])))
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
import heapq
heapq.heapify(a)
BC=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    while BC[i][0]>0:
        if BC[i][1] > a[0]:
            minA = heapq.heappop(a)
            heapq.heappush(a,BC[i][1])
            BC[i][0] -=1
        else:
            break
print((sum(a)))

# Optimized solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
import heapq
heapq.heapify(a)
BC=[list(map(int,input().split())) for _ in range(m)]
BC.sort(reverse=True,key=lambda x:x[1])
for i in range(m):
    while BC[i][0]>0:
        if BC[i][1] > a[0]:
            minA = heapq.heappop(a)
            heapq.heappush(a,BC[i][1])
            BC[i][0] -=1
        else:
            break
print((sum(a)))
# Original solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        heapq.heappop(a)
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heappush(a, (x, y))
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))


# Optimized solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heapreplace(a, (x, y))
        else:
            heapq.heappop(a)
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))
# Original solution
import heapq
from collections import Counter
from itertools import starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(Counter(R()).items())
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heapreplace(a, (x, y))
        else:
            heapq.heappop(a)
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))


# Optimized solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heapreplace(a, (x, y))
        else:
            heapq.heappop(a)
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))