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

def main():
    R, C, K = map( int, input().split())
    V = [[0]*C for _ in range(R)]
    for _ in range(K):
        r, c, v = map( int, input().split())
        V[r-1][c-1] = v
    dp0 = [[0]*(C+1) for _ in range(R+1)]
    dp1 = [[0]*(C+1) for _ in range(R+1)]
    dp2 = [[0]*(C+1) for _ in range(R+1)]
    dp3 = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1,R+1):
        m = 0
        for c in range(1,C+1):
            m = max(m,dp0[r-1][c], dp1[r-1][c], dp2[r-1][c], dp3[r-1][c])
            dp0[r][c] = max(m, dp0[r][c-1])
            dp1[r][c] = max(dp1[r][c-1], dp0[r][c]+V[r-1][c-1])
            dp2[r][c] = max(dp2[r][c-1], dp1[r][c-1]+V[r-1][c-1])
            dp3[r][c] = max(dp3[r][c-1], dp2[r][c-1]+V[r-1][c-1])
    # print(dp0)
    # print(dp1)
    # print(dp2)
    # print(dp3)
    print( max( max(dp0[R]), max(dp1[R]), max(dp2[R]), max(dp3[R])))
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    R, C, K = map( int, input().split())
    V = [[0]*C for _ in range(R)]
    for _ in range(K):
        r, c, v = map( int, input().split())
        V[r-1][c-1] = v
    dp0 = [[0]*(C+1) for _ in range(R+1)]
    dp1 = [[0]*(C+1) for _ in range(R+1)]
    dp2 = [[0]*(C+1) for _ in range(R+1)]
    dp3 = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1,R+1):
        m = 0
        for c in range(1,C+1):
            m = max(m,dp0[r-1][c], dp1[r-1][c], dp2[r-1][c], dp3[r-1][c])
            dp0[r][c] = max(m, dp0[r][c-1])
            dp1[r][c] = max(dp1[r][c-1], dp0[r][c]+V[r-1][c-1])
            dp2[r][c] = max(dp2[r][c-1], dp1[r][c-1]+V[r-1][c-1])
            dp3[r][c] = max(dp3[r][c-1], dp2[r][c-1]+V[r-1][c-1])
    # print(dp0)
    # print(dp1)
    # print(dp2)
    # print(dp3)
    print( max( max(dp0[R]), max(dp1[R]), max(dp2[R]), max(dp3[R])))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95

class vertex:
    def __init__(self):
        self.min_distance = float("inf")
        self.distance = float("inf")
        self.parent = None
        self.minimum_adjacency_list = []
        self.is_in_Q = True
        self.is_in_V = False

def is_single_in_V(v,p):
    a = v[p[0]].is_in_V
    b = v[p[1]].is_in_V
    return ( a and not b ) or ( not a and b )
def all_in_V(v):
    for e in v:
        if not e.is_in_V:
            return False
    return True
def add_in_V(v,pa):
    v[pa[0]].is_in_V = True
    v[pa[1]].is_in_V = True

def solve(nu,mu,du):
    V= []
    E = []
    vertexes = [vertex() for i in xrange(nu)]
    vertexes[0].distance = 0
    V.append(vertexes[0])
    vertexes[0].is_in_V = True
    distances = [ e[2] for e in du ]
    passess = [ e[0:2] for e in du]

    while True:
        if all_in_V(vertexes):
            break
        min_dist = float("inf")
        for i in xrange(len(du)):
            pas = passess[i]
            if is_single_in_V(vertexes,pas):
                min_dist = min( min_dist, distances[i] )
        ind = distances.index(min_dist)
        E.append(min_dist)
        add_in_V(vertexes,passess[ind])
    print sum(E)/100 - len(E)




while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(n):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

### FIXED CODE ###

def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            if ( ( vs[du[i][0]] and not vs[du[i][1]] ) or ( not vs[du[i][0]] and vs[du[i][1]]) ) and min_dist > du[i][2]:
                min_dist,ind,pf,pt = du[i][2],i,du[i][0],du[i][1]
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break

        for i in xrange(len(du)):
            try:
                if vs[du[i][0]] and vs[du[i][1]]:
                    du.pop(i)
            except:
                pass

    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)
### BUGGY CODE ###

n=int(input())
table=[]
for i in range(n):
  table.append([int(_) for _ in input().split()])
T=[[1]*n for i in range(n)]
import itertools
chk,ans=True,0
for Com in itertools.combinations(range(n),3):
  a,b,c=Com[0],Com[1],Com[2]
  lab,lbc,lca=table[a][b],table[b][c],table[c][a]
  if lab>=lbc and lab>=lca:
    if lab>lbc+lca:
      chk=False
    elif lab==lbc+lca:
      T[a][b],T[b][a]=0,0
  elif lbc>=lab and lbc>=lca:
    if lbc>lab+lca:
      chk=False
    elif lbc==lab+lca:
      T[b][c],T[c][b]=0,0
  elif lca>=lab and lca>=lbc:
    if lca>lab+lbc:
      chk=False
    elif lca==lab+lbc:
      T[c][a],T[a][c]=0,0
for i in range(n):
  for j in range(i+1,n):
    if T[i][j]==1:
      ans+=table[i][j]
print(ans if chk==True else -1)

### FIXED CODE ###

n=int(input())
table=[]
for i in range(n):
  table.append([int(_) for _ in input().split()])
T=[[1]*n for i in range(n)]
import itertools
chk,ans=True,0
for Com in itertools.combinations(range(n),3):
  a,b,c=Com[0],Com[1],Com[2]
  lab,lbc,lca=table[a][b],table[b][c],table[c][a]
  if lab>=lbc and lab>=lca:
    if lab>lbc+lca:
      chk=False
    elif lab==lbc+lca:
      T[a][b],T[b][a]=0,0
  elif lbc>=lab and lbc>=lca:
    if lbc>lab+lca:
      chk=False
    elif lbc==lab+lca:
      T[b][c],T[c][b]=0,0
  elif lca>=lab and lca>=lbc:
    if lca>lab+lbc:
      chk=False
    elif lca==lab+lbc:
      T[c][a],T[a][c]=0,0
for i in range(n):
  for j in range(i+1,n):
    if T[i][j]==1:
      ans+=table[i][j]
print(ans if chk==True else -1)
### BUGGY CODE ###

from collections import deque


def main():
    d = deque()
    for _ in range(int(input())):
        d.append(int(input()))
    
    result = min(d) - max(d)

    while d:
        c = d.popleft()
        if not d:
            break

        if max(d) - c > result:
            result = max(d) - c
    
    print(result)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    r = []
    for _ in range(int(input())):
        r.append(int(input()))

    n = len(r)
    maxv = -20000000000
    minv = r[0]

    for i in range(1, n):
        maxv = max([maxv, r[i] - minv])
        minv = min([minv, r[i]])
    
    print(maxv)


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

import sys
import heapq
from collections import Counter

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_s)
a_s.sort()
_max = max(a_s)
que = [(i, i) for i in a_s]
cur = 0
res = set()
while cur <= _max:
    cur, base = heapq.heappop(que)
    if cur != base:
        if cur in a_s:
            res.add(cur)
    else:
        if ct[cur] > 1:
            res.add(cur)
    heapq.heappush(que, (cur + base, base))

print(len(set(a_s)) - len(res))

### FIXED CODE ###

import sys
import heapq
from collections import Counter
from math import sqrt

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
a_s.sort()
_max = max(a_s)
ct = Counter(a_s)
cnt = 0
ls = [False] * (10**6+1)
for a in a_s:
    if ls[a]:
        cnt += 1
        continue
    elif ct[a] > 1:
        cnt += 1
    for i in range(a, _max+1, a):
        if ls[i]:
            continue
        if i % a == 0:
            ls[i] = True

print(n - cnt)
### BUGGY CODE ###

import itertools
from collections import Counter

N, X, Y = map(int, input().split())

xy = 0

n_list = list(range(1,N+1))
n_iter = itertools.combinations(n_list, 2)

count_list = []

for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(Y - i) + abs(X - j) + 1,
    abs(j - i)
  )
  count_list.append(x)

# 要素数の数え上げと取り出し
num_counter = Counter(count_list)
for i in range(1, N):
  if i in num_counter:
    print(num_counter[i])
  else:
    print(0)

### FIXED CODE ###

import itertools

N, X, Y = map(int, input().split())

n_iter = itertools.combinations(list(range(1,N+1)), 2)

count_list = [0]*(N-1)

for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(Y - i) + abs(X - j) + 1,
    abs(j - i)
  )
  count_list[x-1] += 1

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

K , S = map(int, input().split())
x , y , z , cnt = 0 , 0 , 0 , 0
A = K + 1
if K * 3 == S:
    cnt = 1
else :
    for i in range(A):
        x = i
        if x + y + z == S :
            cnt += 1
        for j in range(A):
            y = j
            if x + y + z == S :
                cnt += 1
            for k2 in range(A) :
                z = k2
                if x + y + z == S:
                    cnt += 1

print(cnt)


### FIXED CODE ###

K , S = map(int, input().split())
x , y , z , cnt = 0 , 0 , 0 , 0
A = K + 1
if K * 3 == S:
    cnt = 1
else :
    for i in range(A):
        for j in range(A):
            if  S - (i + j) <= K :
                if 0 <= S - (i + j): 
                    cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        for u, c in links[v]:
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(ans[s - 1][t - 1])

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

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

b = []
while len(a)>=2:
    b.append(a.pop(0))
    b.insert(0, a.pop(0))

if len(a)==1:
    b.append(a.pop(0))
    b.reverse()
    
print(*b)        

### FIXED CODE ###

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

b = []

b_odd = []
b_even = []

for i in range(len(a)):
    if i%2==0:b_even.append(a[i])
    else:b_odd.append(a[i])

if len(a)%2==0:
    b_odd.reverse()
    b_odd+=b_even
    print(*b_odd)
else:
    b_even.reverse()
    b_even+=b_odd
    print(*b_even)
### BUGGY CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
passed = set()
queued = set()
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()
        if (h,w) in passed:
            continue
        passed.add((h,w))
        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))
                queued.add((nh,nw))

        for dh,dw in product(range(-2, 3), repeat=2):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

### FIXED CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([(*c, 0)])
passed = set()
while que:
    h,w,dist = que.popleft()
#         print(f'{h=},{w=}')
    if (h,w) == d:
        print(dist)
        exit()
    if (h,w) in passed:
        continue
    passed.add((h,w))
    for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
            que.appendleft((nh, nw, dist))

    for dh,dw in [
        [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
        [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
        [0,-2], [0, 2], 
        [1,-2], [1,-1], [1, 1], [1, 2], 
        [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
    ]: 
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
            que.append((nh, nw, dist + 1))
print(-1)
### BUGGY CODE ###

N=int(input())
S=str(input())
S=list(S)
ans=S.count('R')*S.count('G')*S.count('B')

for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=(j-i)+j
        if k>N-1:
            continue
        if (S[i] != S[j]) and (S[j] != S[k]) and(S[k] != S[i]) :
            ans -= 1
print(ans)

### FIXED CODE ###

N=int(input())
S=str(input())
S=list(S)
ans=S.count('R')*S.count('G')*S.count('B')
for i in range(N): #判定を簡単にするためR:=1,G:=2,B:=4と置き換えておく
    if S[i]=='R':
        S[i]=1
    elif S[i]=='G':
        S[i]=2
    elif S[i]=='B':
        S[i]=4
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=(j-i)+j
        if k>N-1:
            continue
        if S[i]+S[j]+S[k] == 7 :
            ans -= 1
print(ans)
### BUGGY CODE ###

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

if K%2==1:
    s=K
else:
    s=K//2

ans=[]

for i in range((N-s)//s+1):
    for j in range((N-s)//s+1):
        for k in range(N-s//s+1):
            if s+max(i,j,k)*s <= N and (2+i+j)*s%K==0 and (2+j+k)*s%K==0 and (2+k+i)*s%K==0:
                ans.append((s+i*s,s+j*s,s+k*s))

print(len(set(ans)))

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
 
result = 0
 
if (K%2) == 1:
    kouho = N//K
    result+=kouho*kouho*kouho
 
else:
    kouho1 = N//K
    kouho2 = N//(K/2) - kouho1
    result+=kouho1*kouho1*kouho1
    result+=kouho2*kouho2*kouho2
 
print(int(result))
### BUGGY CODE ###

import sys
import numpy as np

N,K,Q=map(int,sys.stdin.readline().split())
points=np.array([K]*N)
for i in range (Q):
  points=points-1
  points[int(sys.stdin.readline().rstrip())-1]+=1
for b in points>0:
  if b:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

import sys

N,K,Q=map(int,sys.stdin.readline().split())
points=[0]*N
for i in range (Q):
  points[int(sys.stdin.readline().rstrip())-1]+=1
for p in points:
  if (K-(Q-p)) > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

nk=list(map(int,input().split(' ')))
while(True):
    if abs(nk[0]-nk[1])<nk[0]:
        nk[0]=abs(nk[0]-nk[1])
    else:
        break
print(nk[0])

### FIXED CODE ###

nk=list(map(int,input().split(' ')))
nk[0]=nk[0]%nk[1]
while(True):
    if abs(nk[0]-nk[1])<nk[0]:
        nk[0]=abs(nk[0]-nk[1])
    else:
        break
print(nk[0])
### BUGGY CODE ###

n, q = map(int, input().split())
text = input()
cnt = 0
for i in range(q):
    l, r = map(int, input().split())
    target = text[l-1:r]
    for j in range(len(target)-1):
        if target[j]+target[j+1] == "AC":
            cnt += 1
    print(cnt)
    cnt = 0

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
A=[0]*N
for i in range(1,N+1):
	if S[i-1:i+1]=="AC":
		A[i]+=1
for i in range(1,N):
	A[i]=A[i]+A[i-1]
for i in range(Q):
	l,r=map(int,input().split())
	print(A[r-1]-A[l-1])
### BUGGY CODE ###


def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

xs = list(range(1, n))
ys = list(range(n))
ans = sum(a)

for i in xs:
    for j in ys:
        b2[j] = min(a[j], b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

### FIXED CODE ###

def mygets():
    return list(map(int, input().strip().split(' ')))

n, x = mygets()
a = mygets()

b1 = a

ans = sum(a)

def f(k, u):
    j = k - 1
    if j < 0:
        j = n - 1
    w = b1[j]
    if u < w:
        return u
    return w

for i in range(1, n):
    b2 = [f(k, u) for k, u in enumerate(a)]
    ans = min(ans, sum(b2) + i * x)
    b1 = b2

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

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

N = int(input())
X = input()

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

import copy,time

n, k = input().split()
m = list(map(int, input().split()))
ans = 0
kazu =[]
kai = []
kitai = 0
kazu = [(a+1) /2 for a in m]

for x in range(int(n) - (int(k)-1)):
    kitai = kazu[x:x+int(k)]
    if ans < sum(kitai):
        ans = sum(kitai)

print(ans)

### FIXED CODE ###

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

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)
### BUGGY CODE ###

R, G, B, N =list(map(int, input().split()))
# R = 13
# G = 1
# B = 4
# N = 3000
X, Y, Z = sorted([R, G, B], reverse=True)
cnt = 0
for i in range(N+1):
    if (X*i>N): break
    for j in range(N+1):
        if (X*i+Y*j>N): break
        cnt += ((N-X*i-Y*j)%Z == 0)
print(cnt)


### FIXED CODE ###

R, G, B, N =list(map(int, input().split()))
# R = 13
# G = 1
# B = 4
# N = 3000
X, Y, Z = sorted([R, G, B], reverse=True)
cnt = 0
for i in range(N//X+1):
    for j in range(N+1):
        tmp = X*i+Y*j 
        if (tmp>N): break
        cnt += ((N-tmp)%Z == 0)
print(cnt)
### BUGGY CODE ###

import bisect
from collections import Counter
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


n, m = LI()
a = LI()
a = sorted(a)[::-1]
bc = LIR(m)

bc = sorted(bc, key=lambda x: x[1])[::-1]
all_c = []
for bi, ci in bc:
    all_c += [ci] * bi
if len(all_c) < n:
    all_c += [0] * (n - len(all_c))
ans = 0
a_i = 0
c_i = 0
for _ in range(n):
    if a[a_i] > all_c[c_i]:
        ans += a[a_i]
        a_i += 1
    else:
        ans += all_c[c_i]
        c_i += 1
print(ans)


### FIXED CODE ###

import bisect
from collections import Counter
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


n, m = LI()
a = LI()
a = sorted(a)[::-1]
bc = LIR(m)
bc = sorted(bc, key=lambda x: x[1])[::-1]
all_c = []
for bi, ci in bc:
    all_c += [ci] * bi
    if len(all_c) >= n:
        break
if len(all_c) < n:
    all_c += [0] * (n - len(all_c))

ans = 0
a_i = 0
c_i = 0
for _ in range(n):
    if a[a_i] > all_c[c_i]:
        ans += a[a_i]
        a_i += 1
    else:
        ans += all_c[c_i]
        c_i += 1
print(ans)