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

# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                dp[jw] = max(dp[jw], dpj + v)
                max_w = max(max_w, jw)
    print(max(dp))


main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

for i in A:
    print(int(i),end=' ')
print()

### FIXED CODE ###

import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

for i in A:
    print(int(i),end=' ')
print()
### BUGGY CODE ###

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

G = [[float('inf')] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c


for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if G[i][j] > G[i][k] + G[k][j]:
                G[i][j] = G[i][k] + G[k][j]

GL = [[float('inf')] * (N+1) for _ in range(N+1)]
for i in range(1, N):
    for j in range(i+1, N+1):
        if G[i][j] <= L:
            GL[i][j] = 1
            GL[j][i] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if GL[i][j] > GL[i][k] + GL[k][j]:
                GL[i][j] = GL[i][k] + GL[k][j]

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = GL[s][t]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans-1)




### FIXED CODE ###

N, M, L = map(int, input().split())
INF = 10 ** 12

G = [[INF] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c


for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

GL = [[INF] * (N+1) for _ in range(N+1)]
for i in range(1, N):
    for j in range(i+1, N+1):
        if G[i][j] <= L:
            GL[i][j] = 1
            GL[j][i] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            GL[i][j] = min(GL[i][j], GL[i][k] + GL[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = GL[s][t]
    if ans == INF:
        print(-1)
    else:
        print(ans-1)
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
td_arr = []
for _ in range(N):
    td = tuple(int(x) for x in input().split())
    td_arr.append(td)

td_arr.sort(key=lambda x:x[1], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for t,d in td_arr[:K]:
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

candidate_dict = {}
candidate_dict[len(n_dm_set)] = d_dm

prev_t = -1
other_arr = []
for t,d in sorted(td_arr, key=lambda x:x[0]):
    if t == prev_t:
        continue
    if t in n_dm_set:
        continue
    prev_t = t
    other_arr.append((t,d))
other_arr.sort(key=lambda x:x[1], reverse=True)

d_x = d_dm
nt_x = len(n_dm_set)
for t,d in other_arr:
    if len(small_arr) == 0:
        break
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    nt_x += 1
    candidate_dict[nt_x] = d_x

ans = 0
for k,v in candidate_dict.items():
    ans = max(ans, k*k+v)

print(ans)


### FIXED CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(list(map(int, input().split())))

i_count = 1
for i in range(1, N):
  if (P[:i] < P[i]).any() == False:
    i_count +=1
  
print(i_count)

### FIXED CODE ###

import sys
sysinput = sys.stdin.readline

N = int(sysinput())
P = list(map(int, sysinput().split()))
memo_mini = N
i_count = 0
for i in range(0, N):
  if memo_mini >= P[i]:
      i_count +=1
      memo_mini = P[i]
  else:
    pass
  
print(i_count)
### BUGGY CODE ###

from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

from heapq import heappush, heappop
dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
while que:
    cost, i, j = heappop(que)
    if dist[i][j] < cost:
        continue
    if i == j == N:
        print(cost)
        break
    if i < N and cost + P[i][j] < dist[i+1][j]:
        dist[i+1][j] = d = cost + P[i][j]
        heappush(que, (d, i+1, j))
    if j < N and cost + Q[j][i] < dist[i][j+1]:
        dist[i][j+1] = d = cost + Q[j][i]
        heappush(que, (d, i, j+1))


### FIXED CODE ###

from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])
### BUGGY CODE ###

def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)

K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=gcd(i,gcd(j,k))
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)

K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=gcd(i,gcd(j,k))
print(ans)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
b=sorted(list(map(int,input().split())),reverse=True)
c=sorted(list(map(int,input().split())),reverse=True)
ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(reverse=True)
ans=[]
for i in range(min(k,x*y)):
    for j in range(z):
        ans.append(ab[i]+c[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
b=sorted(list(map(int,input().split())),reverse=True)
c=sorted(list(map(int,input().split())),reverse=True)
ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(reverse=True)
ans=[]
for i in range(min(k,x*y)):
    for j in range(z):
        ans.append(ab[i]+c[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

while 1:
	try:
		stack = []
		st = map(str, raw_input().split())
		for s in st:
			if s == "-":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) * stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) / stack.pop())
			else:
				stack.append(float(s))
	
		print stack[0]
	except:
		pass

### FIXED CODE ###

while 1:
	try:
		stack = []
		for s in raw_input().split():
			if s == "-":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) / stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) * stack.pop())
			else:
				stack.append(float(s))
	
		print "%.6f" % (stack[0])
	except:
		break
### BUGGY CODE ###

k = int(input())

import math
from collections import deque
ans = deque()
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            ans.append(math.gcd(math.gcd(i, j), l))
print(sum(ans))


### FIXED CODE ###

k = int(input())

import math
ans = 0
ans1 = 0
ans2 = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans1 += math.gcd(i,j)

ans = ans + ans1*3

for i in range(1,k+1):
    for j in range(1,i):
        for l in range(1,j):
            ans2 += math.gcd(math.gcd(i,j),l)

ans += ans2*6
print(ans-sum(list(range(k+1)))*2)
### BUGGY CODE ###

N, M = map(int, input().split())
P = []
for i in range(M):
    a, b, c = map(int, input().split())
    P.append((a-1, b-1, -c))

Cost = [float("inf") for i in range(N)]
Cost[0] = 0
for i in range(N-1):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            Cost[j[1]] = Cost[j[0]] + j[2]     
ans = -Cost[N-1]

Cost = [float("inf") for i in range(N)]
V = [False for i in range(N)]
Cost[0] = 0
for i in range(N):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            if Cost[j[1]] != float("inf"):
                V[j[1]] = True
            Cost[j[1]] = Cost[j[0]] + j[2]    
        if V[j[0]] == True:
            V[j[1]] = True

print("inf" if V[N-1] else ans)

### FIXED CODE ###

N, M = map(int, input().split())
P = []
for i in range(M):
    a, b, c = map(int, input().split())
    P.append((a-1, b-1, -c))

Cost = [float("inf") for i in range(N)]
V = [False for i in range(N)]
Cost[0] = 0
for i in range(N-1):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            if Cost[j[1]] != float("inf"):
                V[j[1]] = True
            Cost[j[1]] = Cost[j[0]] + j[2]     
        if V[j[0]] == True:
            V[j[1]] = True
ans = -Cost[N-1]

for j in P:
    if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
        if Cost[j[1]] != float("inf"):
            V[j[1]] = True
        Cost[j[1]] = Cost[j[0]] + j[2]    
    if V[j[0]] == True:
        V[j[1]] = True

print("inf" if V[N-1] else ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
maxp = 0
for i in range(n - k + 1):
    sump = sum(p[i: i + k])
    if maxp < sump:
        maxp = sump
        j = i
print((maxp + k) / 2)


### FIXED CODE ###

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
expp = [(i + 1) / 2 for i in p]
cumu, cumu_expp = 0, []
for i in expp:
    cumu += i
    cumu_expp.append(cumu)

max_expp = cumu_expp[k - 1]
for i in range(n - k):
    sumpk = cumu_expp[i + k] - cumu_expp[i]
    if max_expp < sumpk:
        max_expp = sumpk
print(max_expp)
### BUGGY CODE ###

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

minimum_cost = [abs(H[i] - H[0]) for i in range(min(K+1, N))] \
               + [float('inf') for i in range(N-min(K+1, N))]

for i in range(2, N):
    for j in range(K+1):
        if i-j < 0:
            break
        temp = minimum_cost[i-j] + abs(H[i]-H[i-j])
        minimum_cost[i] = min(temp, minimum_cost[i])

print(minimum_cost[N-1])

### FIXED CODE ###

import numpy as np

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

minimum_cost = np.zeros(N, dtype=int)
H = np.array(H)

for i in range(1, N):
    start = max(0, i-K)
    minimum_cost[i] = min(minimum_cost[start:i]
                          + np.abs(H[i] - H[start:i]))

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

l, r = list(map(int,input().split()))
mod = 2019
min = 2019
for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
        if min > (i * j) % mod:
            min = (i * j) % mod
print(min)

### FIXED CODE ###

l, r = list(map(int,input().split()))
mod = 2019
min = 2019
for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
        if min > (i * j) % mod:
            min = (i * j) % mod
        if min == 0:
            print(0)
            exit()
print(min)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

positions = {}
positions['R'] = [i for i in range(n) if s[i]=='R']
positions['G'] = [i for i in range(n) if s[i]=='G']
positions['B'] = [i for i in range(n) if s[i]=='B']
positions['RG'] = sorted(positions['R']+positions['G'])
positions['RB'] = sorted(positions['R']+positions['B'])
positions['GB'] = sorted(positions['G']+positions['B'])

for p1 in range(n-3):
    if s[p1] == 'R':
        pos2 = positions['GB']
    elif s[p1] == 'G':
        pos2 = positions['RB']
    else:
        pos2 = positions['RG']

    for p2 in pos2:
        if p2 > p1:
            for p3 in pos2:
                if p3 > p2:                
                    #print(s[p1], s[p2], s[p3])
                    if (s[p1] != s[p2]) and (s[p1] != s[p3]) and (s[p2] != s[p3]) and (p1-p2 != p2-p3):
                        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dup = 0
r = s.count('R')
g = s.count('G')
b = s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2*j - i
        if k < n:
            #print(i,j,k)
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[i] != s[k]):
                #print(s[i], s[j], s[k])
                dup += 1
print(r*g*b - dup)
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w1 = input()
if w1 == 'Vacant':
    exit()

l, r = 0, N
while r - l > 2:
    m = (l + r) // 2
    print(m, flush=True)
    w2 = input()
    if w2 == 'Vacant':
        exit()

    if w1 == w2:
        l, r = (l, m) if (m - l) % 2 == 1 else (m, r)
    else:
        l, r = (m, r) if (m - l) % 2 == 1 else (l, m)
    w1 = w2
print((l + r) // 2, flush=True)
exit()


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
target_list = np.array([int(i) for i in input().split()])
if N>M:
    print(0)
else:
    target_list = np.sort(target_list)
    diff_list = target_list[1:] - target_list[:-1]
    for i in range(0, N-1):
        diff_list = np.delete(diff_list, np.argmax(diff_list))
    print(np.sum(diff_list))

### FIXED CODE ###

import numpy as np
N, M = map(int,input().split())
target_list = np.array([int(i) for i in input().split()])
if N > M:
    print(0)
else:
    target_list = np.sort(target_list)
    diff_list = target_list[1:] - target_list[:-1]
    diff_list = np.sort(diff_list)
    if N > 1:
        diff_list = diff_list[0:-(N-1)]
    print(np.sum(diff_list))
### BUGGY CODE ###

from collections import Counter as coun
from itertools import combinations as comb

import sys
input = sys.stdin.readline

N = int(input())
S = input()
C = coun(S)
r, g, b = C["R"], C["G"], C["B"]
count = r * g * b

for i, j in comb(range(N), 2):
  k = 2 * j - i
  if 0 <= k < N:
    a, b, c = S[i], S[j], S[k]
    if a != b and b != c and c != a: count -= 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

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

from itertools import product
from bisect import bisect_left


def read():
    N = int(input())
    XYP = []
    for i in range(N):
        x, y, p = map(int, input().split())
        XYP.append((x, y, p))
    return N, XYP



def solve(N, XYP, INF=1<<61):
    # 3^N通り全て試す
    # 東西、左右、道なしの3通り
    minK = [INF for i in range(N+1)]

    for ptn in product(range(3), repeat=N):
        nh = ptn.count(1)
        nv = ptn.count(2)
        k = nh + nv
        # calculate score
        score = 0
        nearest_x = [abs(x)*p for x, y, p in XYP]
        nearest_y = [abs(y)*p for x, y, p in XYP]
        for i in range(N):
            x, y, p = XYP[i]
            for j in range(N):
                x1, y1, p1 = XYP[j]
                if ptn[j] == 1:
                    nearest_x[i] = min(nearest_x[i], abs(x - x1)*p)
                elif ptn[j] == 2:
                    nearest_y[i] = min(nearest_y[i], abs(y -y1) * p)
                
        for i in range(N):
            score += min(nearest_x[i], nearest_y[i])
        minK[k] = min(minK[k], score)
    
    for k in range(0, N+1):
        print(minK[k])
    


if __name__ == '__main__':
    inputs = read()
    solve(*inputs)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((2**N, N), dtype=np.int32)
    hcost = np.zeros((2**N, N), dtype=np.int32)

    # check 2**N pairs
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[intptn, i] += v
            hcost[intptn, i] += h

    # check 3**N pairs
    for intptn in range(3**N):
        # split into two 2**N pairs
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[intvptn, i], hcost[inthptn, i]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)
### BUGGY CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
for m in range(M):
  B, C = map(int, input().split())
  As.sort()
  for i in range(B):
    if As[i] < C:
      As[i] = C
print(sum(As))


### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
BCs = []
for m in range(M):
  B, C = map(int, input().split())
  BCs.append((B, C))
BCs.sort(key=lambda BC: -BC[1])
#print(BCs)

index = 0
for m in range(M):
  B, C = BCs[m]
  for i in range(B):
    if index >= N:
      break
    if As[index] < C:
      As[index] = C
      index += 1
    else:
      break
print(sum(As))
### BUGGY CODE ###

N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []

for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break

for i in range(Q):
    l, r = (int(i) for i in input().split())
    result = [i for i in onon if i >= l and i <= (r - 1)]
    print(len(result))

### FIXED CODE ###

import bisect
N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []
for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break
for i in range(Q):
    l, r = (int(i) for i in input().split())
    left = bisect.bisect_left(onon,l)
    right = bisect.bisect_left(onon,r)
    print(right - left)
### BUGGY CODE ###

import math

n,m = map(int,input().split())
flag = False

for i in range(2,int(math.sqrt(m)+1)):
    if m % i == 0:
        flag = True
        break

if flag == True:
    for i in range(int(m/n),0,-1):
        if m % i == 0:
            print(i)
            break
else:
    print(1)

### FIXED CODE ###

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

def yakusuu(n,m):
    for i in range(int(m/n),0,-1):
        if m % i == 0:
            print(i)
            break

yakusuu(n,m)
### BUGGY CODE ###

import math

q = int(input())


n = 100000
primes = set(range(2, n+1))

for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))

primes = list(primes)


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    for i in range(l, r + 1, 2):
        tmp += i in primes and (i + 1) // 2 in primes
    ans.append(tmp)

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

### FIXED CODE ###

import numpy as np

q = int(input())

# 素数列挙
n = 10**5 + 1
primes = set(range(3, n+1, 2))
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True

like_2017 = like_2017.cumsum()


def cnt_primes(l, r):
    return like_2017[r] - like_2017[l - 1]


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

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