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

n, k = map(int, input().split())
s = input()
turn = 0

happiness = 0


def exchange(num, loc):
    global s
    tmp = s[loc:loc+num+1]
    tmp = tmp[::-1]
    tmp = ['L' if x == 'R' else 'R' for x in tmp]
    s[loc:loc+num+1] = tmp

for i in range(n):
    if i == 0:
        if s[i] == 'R' and s[i+1] == 'R':
            happiness += 1
    elif i == n-1:
        if s[i] == 'L' and s[i-1] == 'L':
            happiness += 1
    else:
        if s[i] == 'R' and s[i+1] == 'R':
            happiness += 1
        elif s[i] == 'L' and s[i-1] == 'L':
            happiness += 1

for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L' or s[i] == 'L' and s[i+1] == 'R':
        turn += 1


s = 'X' + s + 'X'
s = list(s)
lamp = -1
while k != 0:
    lamp += 1
    if turn == 1:
        print(n-1)
        exit()
    for j in range(2, n-lamp-1):
        if s[j] == 'R' and s[j - 1] != 'R' and s[j + lamp] == 'R' and s[j + lamp + 1] != 'R':
            happiness += 2
            exchange(lamp, j)
            k -= 1
            turn -= 2
            break
        elif s[j] == 'L' and s[j - 1] != 'L' and s[j + lamp] == 'L' and s[j + lamp + 1] != 'R':
            happiness += 2
            exchange(lamp, j)
            k -= 1
            turn -= 2
            break
    if turn == 0:
        break

print(happiness)


### FIXED CODE ###

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

s = list(s)

li = []
que = []
for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(i)
li.append(n-1)
if len(li) == 1:
    print(n-1)
    exit()

for i in range(0,len(li)-1, 2):
    if k > 0:
        char = s[li[i]]
        a = s[li[i]+1:li[i+1]+1]
        s[li[i]+1:li[i+1]+1] = char * (li[i+1] - li[i])
    k -= 1

happiness = 0

for i in range(n):
    if i == 0:
        if s[i] == 'R' and s[i+1] == 'R':
            happiness +=1
    elif i == n-1:
        if s[i] == 'L' and s[i-1] == 'L':
            happiness += 1
    else:
        if s[i] == 'R' and s[i + 1] == 'R':
            happiness += 1
        elif s[i] == 'L' and s[i - 1] == 'L':
            happiness += 1

print(happiness)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())

result = 0
#memo = {}


def terasu(x, y, d):
    #print(x, y, h, w)
    if y < 0 or x < 0 or y >= h or x >= w:
        return 0
    # if (x, y) in memo.keys():
    #    return 0
    if s[y][x] == "#":
        return 0
    #memo[(x, y)] = True
    if d == "f":
        return 1 + terasu(x + 1, y, "e") + terasu(x, y - 1, "s") + terasu(x, y+1, "n") + terasu(x-1, y, "w")
    elif d == "e":
        return 1 + terasu(x + 1, y, "e")
    elif d == "s":
        return 1 + terasu(x, y - 1, "s")
    elif d == "n":
        return 1 + terasu(x, y+1, "n")
    elif d == "w":
        return 1 + terasu(x-1, y, "w")


for y in range(h):
    for x in range(w):
        result = max(result, terasu(x, y, "f"))
print(result)

### FIXED CODE ###

#解説コードコピペです

import numpy as np
 
def solve():
    H, W = list(map(int, input().split()))
    grid = []
    for i in range(H):
        grid.append(list(input()))
    #print((np.array(grid) == ".") * 1) #行列演算 "." ならTrue そうでなければFalseの行列をつくる *1で1と0に変換
    grid = (np.array(grid) == ".") * 1  # ランプをおける:1, 障害物:0
 
    L = np.zeros((H,W), dtype=int) #0でうめつくした行列をつくる
    R = np.zeros((H,W), dtype=int)
    U = np.zeros((H,W), dtype=int)
    D = np.zeros((H,W), dtype=int)
    
    for j in range(W): #列単位で処理
        if j == 0:
            L[:, j] = grid[:, j]
        else:
            L[:, j] = (L[:, j-1] + 1) * grid[:, j] #gridでかけることで 障害物があったときにそのマスを0にする
    
    for j in range(W-1, -1, -1):
        if j == W-1:
            R[:, j] = grid[:, j]
        else:
            R[:, j] = (R[:, j+1] + 1) * grid[:, j]
 
    for i in range(H):
        if i == 0:
            U[i] = grid[i] * 1
        else:
            U[i] = (U[i-1] + 1) * grid[i]
    
    for i in range(H-1, -1, -1):
        if i == H-1:
            D[i] = grid[i]
        else:
            D[i] = (D[i+1] + 1) * grid[i]
 
    ans = np.max(L+R+U+D-3)
    print(ans)
 
 
if __name__ == "__main__": #ここはしらん
    solve()
### BUGGY CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        nn = n-j
        if s[i] == s[j]:
            continue
        w = j - i
        if j+w < n and (s[j+w] != s[j] and s[j+w] != s[i]):
            cnt -= 1
        not_same = nn - (s[j:].count(s[i]) + s[j:].count(s[j]))
        cnt += not_same

print(cnt)


### FIXED CODE ###

from collections import Counter

n = int(input())
s = input()
c = Counter(s)
cnt = c['R'] * c['G'] * c['B']

for i in range(n-2):
    for j in range(i+1, n-1):
        w = j - i
        if j+w >= n:
            continue
        if s[i] != s[j] and s[j+w] != s[j] and s[j+w] != s[i]:
            cnt -= 1

print(cnt)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list( map(int, input().split()))
p = 10**9+7

len_max = len(list(format(max(a), 'b')))

bin_list = np.array([0]*len_max)

for a_ in a:
    a_bin = np.array( list(map(int ,list(format(a_,'b').zfill(len_max)))))
    bin_list += a_bin


ans = 0
for i in range(1,len_max+1):
    num_1 = bin_list[-i]%p
    ans += 2**(i-1)%p * num_1 * (n-num_1)%p

print(ans%p)

### FIXED CODE ###

n = int(input())
a = list( map(int, input().split()))
p = 10**9+7

len_max = len(list(format(max(a), 'b')))

bin_list = [0]*len_max

for a_ in a:
    for i in range(1,len_max+1):
        if a_ & (1<<(i-1)):
            bin_list[-i] += 1

ans = 0
for i in range(1,len_max+1):
    num_1 = bin_list[-i]%p
    ans += 2**(i-1)%p * num_1 * (n-num_1)%p

print(ans%p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


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


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A = zz()
hyouka = [1] * (N)

for i in range(K - 1, N):
    for j in range(K):
        # print(j)
        hyouka[i] *= A[i-j]
# print(hyouka)
prev = hyouka[K-1]
for now in hyouka[K:]:
    if (prev < now):
        print('Yes')
    else:
        print('No')
    prev = now


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


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


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A = zz()

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

import collections

N = int(input())

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

num_count = collections.Counter(x)

key_list = list(set(x))
key_list.sort()

cnt = 0
flg = True
n = 0
center_num = N // 2

for i in x:
    j = 0
    while cnt < center_num:
        n = key_list[j]
        if flg and i == n:
            cnt += num_count[n]-1
            flg = False
        else:
            cnt += num_count[n]
        j += 1
    print(n)
    cnt = 0
    flg = True

### FIXED CODE ###

import copy

N = int(input())

x = list(map(int,input().split()))
sort_x = copy.copy(x)
sort_x.sort()

center_num = (N-1) // 2

for l in x:
    if l <= sort_x[center_num]:
        print(sort_x[center_num+1])
    else:
        print(sort_x[center_num])
### BUGGY CODE ###

from collections import deque
import itertools

N = int(input())
V = list(map(int, input().split()))
l = list(itertools.permutations(V))
r = list()
for lo in l:
    d = deque(lo)
    while(len(d) != 1):
        d.append((d.pop() + d.pop()) / 2)
    r.append(d)
print(max(r).pop())


### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
V.sort()
a = V[0]
for i in range(1, N):
    a = (a + V[i])/2
print(a)
### BUGGY CODE ###

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

s_t = set()
for i in range(n):
    s_t.add(int(input()))

print(len(s_t.difference(set(range(a, b)))))


### FIXED CODE ###

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

s_t = set()
for i in range(n):
    s_t.add(int(input()))
answer = 0
for s in s_t:
    if a <= s < b:
        pass
    else:
        answer += 1
print(answer)
### BUGGY CODE ###

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

p = [0] * n

for i, num in enumerate(p):
  for j in a:
    if(i == j - 1):
      p[i] += 1

for i in p:
  print(i)


### FIXED CODE ###

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

p = [0] * n

for i in a:
    p[i - 1] += 1

for i in p:
  print(i)
### BUGGY CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])
Q = int(s[2])

point = [K for i in range(N)]

A = [0 for i in range(Q)]

for i in range(Q):
    A[i] = int(input())
    for j in range(N):
        if j == A[i]-1:
            continue
        else:
            point[j] -= 1

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


### FIXED CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])
Q = int(s[2])

point = [K-Q for i in range(N)]


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

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

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

for i in range(1, N+1):
    print(A.count(i))

### FIXED CODE ###

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

C = [0] * (N+1)
for i in range(N-1):
    C[A[i]] += 1

for i in range(1, N+1):
    print(C[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))
k = [[x,i] for i,x in enumerate(k)]
k.sort()

ans = [[0,-1] for i in range(q)]
for i in range(q):
    ans[i][1] = k[i][1]

def search(x):
    ind = x
    m = 0
    c = 0
    count = 0
    for num,i in enumerate(k):
        while ind+count < n and count < i[0]:
            if s[ind+count] == "M":
                m += 1
            elif s[ind+count] == "C":
                c += 1
                ans[num][0]+=m
            count += 1
    
for i in range(n):
    if s[i] == "D":
        search(i)

for i in range(1,q):
    ans[i][0] += ans[i-1][0]
ans.sort(key=lambda x: x[1])
for i,j in ans:
    print(i)

### FIXED CODE ###

from collections import deque
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    q = deque([])
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
            q.append(d)
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1
                
        
    return ans
for i in k:
    print(search(i))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

l = []
AA = A.copy()
for k in range(N):
    Amin = min(AA)
    for i in range(len(A)):
        a = A[i]
        if Amin == a:
            l.append(i + 1)
    AA.remove(Amin)
print(*l)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

l = [0] * N

for i, a in enumerate(A):
    l[int(a - 1)] = str(i + 1)
print(*l)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# B - Sum of Three Integers
K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z != S:
                continue
            count += 1

# 出力
print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# B - Sum of Three Integers
K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >= 0 and z <= K:
            count += 1

# 出力
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
tmpa = list(map(int, range(l, r+1)))
for i in range(m-1):
    l, r = map(int, input().split())
    ret = []
    for j in range(l, r+1):
        if j in tmpa:
            ret.append(j)

    tmpa = ret.copy()

print(len(tmpa))

### FIXED CODE ###

n, m = map(int, input().split())
ls = []
rs = []
for i in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)

print(max(min(rs)-max(ls)+1, 0))
### BUGGY CODE ###

import sys


class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*2**(self.K+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X-1] = v

        for i in range(2*X-2, 0, -2):
            self.seg[(i-1) >> 1] = self.f(self.seg[i], self.seg[i-1])

    def update(self, k, value):
        X = 2**self.K
        k += X-1
        self.seg[k] = value
        while k:
            k = (k-1) >> 1
            self.seg[k] = self.f(self.seg[(k << 1)+1], self.seg[(k << 1)+2])

    def query(self, L, R):
        num = 2**self.K-1
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1 == 0:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1 == 0:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


input = sys.stdin.readline


def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    que = [tuple(input().split()) for i in range(Q)]
    alpha = "abcdefghijklmnopqrstuvwxyz"
    Data = {alpha[i]: [0]*N for i in range(26)}
    for i in range(N):
        Data[S[i]][i] += 1
    SEG = {alpha[i]: SegTree(Data[alpha[i]], max, 0) for i in range(26)}
    for X, u, v in que:
        if X == "1":
            u = int(u)-1
            NOW = S[u]
            S[u] = v
            SEG[NOW].update(u, 0)
            SEG[v].update(u, 1)
        else:
            u, v = int(u)-1, int(v)-1
            res = 0
            for j in range(26):
                res += SEG[alpha[j]].query(u, v+1)
            print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#segtree ライブラリ
#BITライブラリの作成
#リストの要素を1,0で長さをｎとした時に使える
class BIT:
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        return self.to_sum(j)-self.to_sum(i-1)
n=int(input())
s=list(input())
q=int(input())
que=[]

for i in range(q):
    p=list(input().split())
    que.append(p)
alpha="abcdefghijklmnopqrstuvwxyz"
segtree={alpha[i]:BIT(n) for i in range(26)}  
for i in range(n):
    segtree[s[i]].add(i+1,1)
for q in que:
    x,y,z=q[0],q[1],q[2]
    if int(x)==1:
        #y文字目をzに変更する
        y=int(y)  
        for i in range(26):
            if segtree[alpha[i]].get(y,y)==1:
                segtree[alpha[i]].add(y,-1)
                break
        segtree[z].add(y,1)
    else:
        ans=0
        for i in range(26):
            if segtree[alpha[i]].get(int(y),int(z))>0:
                ans+=1
        print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = max(dp[c], profits + dp[c - weights])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        if ans > 1 and (abs(sh - gh) + abs(sw - gw) <= 1):
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                        else:
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                            visited = [[-1] * W for _ in range(H)]
                            step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                            ans = max(ans, step_cnt)
    print(ans - 1)


### FIXED CODE ###

from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    KLR = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[2]-x[1])
    line = [-1]*N
    ans = 0
    for k, l, r in KLR:
        if l < r:
            break
        flg = False
        for i in range(k-1, -1, -1):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += l
        else:
            ans += r
    line = [-1] * N
    for k, l, r in KLR[::-1]:
        if l >= r:
            break
        flg = False
        for i in range(k, N):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += r
        else:
            ans += l
    print(ans)


for _ in range(T):
    solve()


### FIXED CODE ###

import sys
import heapq


input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    ls = []
    rs = []
    heapq.heapify(ls)
    heapq.heapify(rs)
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l - r >= 0:
            heapq.heappush(ls, (k, l, r))
        else:
            heapq.heappush(rs, (N-k, l, r))
    ans = 0
    ls_l = []
    heapq.heapify(ls_l)
    while len(ls) != 0:
        k, l, r = heapq.heappop(ls)
        heapq.heappush(ls_l, (l-r))
        ans += r
        while len(ls_l) > k:
            heapq.heappop(ls_l)
    rs_r = []
    heapq.heapify(rs_r)
    while len(rs) != 0:
        k, l, r = heapq.heappop(rs)
        heapq.heappush(rs_r, (r-l))
        ans += l
        while len(rs_r) > k:
            heapq.heappop(rs_r)
    while len(ls_l) != 0:
        ans += heapq.heappop(ls_l)
    while len(rs_r) != 0:
        ans += heapq.heappop(rs_r)
    print(ans)


for _ in range(T):
    solve()
### BUGGY CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a = sorted(a)
    ops = sorted(ops, reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        for i, a_i in enumerate(a[start:]):
            if a_i < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[start+i] = ope
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)
### BUGGY CODE ###

import sys
from bisect import bisect_right
input = sys.stdin.readline

n, m = map(int, input().split())
ba = []
for _ in range(n):
    a, b = map(int, input().split())
    ba.append([b, a])
ba.sort(reverse=True)
days = [x for x in range(m)]
ans = 0
for x in ba:
    a = x[1]
    b = x[0]
    lim = m - a
    d = bisect_right(days, lim)
    if d > 0:
        ans += b
        days = days[:d-1] + days[d:]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import *


n, m = map(int, input().split())
tmp = [ [] for _ in range(10 ** 5 + 1) ]
for _ in range(n):
    a, b = map(int, input().split())
    tmp[a].append(b)

h = []
ans = 0
for i in range(1, m+1):
    for bb in tmp[i]:
        heappush(h, -bb)
    if h:
        ans += -heappop(h)
print(ans)