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

n,k=map(int,input().split())
P=[int(i) for i in input().split()]
num=2**(n-1).bit_length()
def init1(init_val):
  for i in range(n):
    seg1[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
      seg1[i]=max(seg1[2*i+1],seg1[2*i+2]) 
def init2(init_val):
  for i in range(n):
    seg2[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
      seg2[i]=min(seg2[2*i+1],seg2[2*i+2]) 
   
def query1(p,q):
  if q<=p:
    return ide_ele1
  p+=num-1
  q+=num-2
  res=ide_ele1
  while q-p>1:
    if p&1==0:
      res=max(res,seg1[p])
    if q&1==1:
      res=max(res,seg1[q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=max(res,seg1[p])
  else:
    res=max(max(res,seg1[p]),seg1[q])
  return res
def query2(p,q):
  if q<=p:
    return ide_ele2
  p+=num-1
  q+=num-2
  res=ide_ele2
  while q-p>1:
    if p&1==0:
      res=min(res,seg2[p])
    if q&1==1:
      res=min(res,seg2[q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=min(res,seg2[p])
  else:
    res=min(min(res,seg2[p]),seg2[q])
  return res
ide_ele1=0
ide_ele2=n
seg1=[ide_ele1]*2*num
seg2=[ide_ele2]*2*num
init1(P)
init2(P)
ans=1
for i in range(k,n):
  if P[i-k]==query2(i-k,k+1) and P[i]==query1(i-k,k+1):
    continue
  else:
    ans+=1

Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]>=k-1:
    count+=1
print(ans-max(0,count-1))

### FIXED CODE ###

n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(0)
for i in range(1,n):
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  if i<k:
    continue
  else:
    A1.append(P[M1[0]])
M2.append(0)
for i in range(1,n):
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==P[i+k]:
    continue
  else:
    ans+=1
Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]==k-1:
    count+=1
print(ans-max(0,count-1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N,K=map(int,input().split())
tree=[[]for _ in range(N+1)]
MOD=10**9+7
ans=K
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
def enu(a,b):
    num=1
    for i in range(b):
        num=num*(a-i)
        num%=MOD
    return num
def dfs(a,b):
    if a==1:
        node=len(tree[a])
        ret=enu(K-1,node)%MOD
    else:
        node=len(tree[a])-1
        ret=enu(K-2,node)%MOD
    for i in tree[a]:
        if i==b:
            continue
        ret=ret*dfs(i,a)%MOD
    return ret
ans*=dfs(1,0)
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N,K=map(int,input().split())
tree=[[]for _ in range(N+1)]
MOD=10**9+7
ans=K
enuk=[1]*(N)
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    enuk[i+1]=(enuk[i]*(K-2-i))%MOD
def dfs(a,b):
    if a==1:
        node=len(tree[a])
        ret=1
        for i in range(node):
            ret*=K-1-i
            ret%=MOD
    else:
        node=len(tree[a])-1
        ret=enuk[node]%MOD
    for i in tree[a]:
        if i==b:
            continue
        ret=ret*dfs(i,a)%MOD
    return ret
ans*=dfs(1,0)
print(ans%MOD)
### BUGGY CODE ###

#from collections import deque
#import copy

x,y,z,ansk=(int(i) for i in input().split())
#print(x,y,z,k)

a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

mylist=[0 for i in range(x*y)]
k=0
for i in range(x):
  for j in range(y):
    mylist[k]=a[i]+b[j]
    k+=1
mylist.sort(reverse=True)
#print(mylist)

k=0
mylist1=[0 for i in range(x*y*z)]
for i in range(x*y):
  for j in range(z):
    mylist1[k]=mylist[i]+c[j]
    k+=1
mylist1.sort(reverse=True)

for i in range(ansk):
  print(mylist1[i])

### FIXED CODE ###

#import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

#k=3000
#a=[int(i) for i in range(1000)]
#b=[int(i) for i in range(1000)]
#c=[int(i) for i in range(1000)]
x=[]
for h in range(len(a)):
    for i in range(len(b)):
        if (h+1)*(i+1) <=k:
            for j in range(len(c)):
                if (h+1)*(i+1)*(j+1) <=k:
                    x.append(a[h]+b[i]+c[j])

x.sort(reverse=True)
for i in range(k):
  print(x[i])
### BUGGY CODE ###


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


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする


# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 10**5
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)


### FIXED CODE ###



# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

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

import sys

for line in sys.stdin:
  try:
    n = int(line)
    primes = [2]
    for i in range(3, n + 1):
      primes.append(i)
      for p in primes:
        if i % p == 0 and i != p:
          primes.pop()
          break
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break

### FIXED CODE ###

import sys
import math

# Sieve of Eratosthenes
N = 999999
searchList = list(range(3, N + 1, 2))
primes = [2]
while True:
  top = searchList.pop(0)
  primes.append(top)
  if top > math.sqrt(N):
    break
  searchList = [s for s in searchList if s % top != 0]
primes.extend(searchList)

# solve
for line in sys.stdin:
  try:
    n = int(line)
    ans = [i for i in primes if i <= n]
    print(len(ans))
  except:
    break
### BUGGY CODE ###

def countDivBy(d,a,b):
    x=d
    res=0
    while (x<a):
        x+=d
    while (x<=b):
        x+=d
        res+=1
    return res
 
def gcd(c,d):
    if(d>c):
        c,d = d,c
    a,b=c,d
    r=a%b
    while (r>0):      
        a = b
        b = r 
        r = a%b
    return b

A = list(map(int, input().split()))
a, b, c, d = A
g = gcd(c,d)
lcm = int(c*d/g)
ans = b - a + 1 - countDivBy(c,a,b) - countDivBy(d,a,b) + countDivBy(lcm,a,b)
print(ans)

### FIXED CODE ###

def countDivBy(d,a,b):
    resB=b//d
    resA=(a-1)//d
    res = resB-resA
    return res

def gcd(c,d):
    if(d>c):
        c,d = d,c
    a,b=c,d
    r=a%b
    while (r>0):      
        a = b
        b = r 
        r = a%b
    return b
  
A = list(map(int, input().split()))
a, b, c, d = A
g = gcd(c,d)
lcm = (c*d) // g
ans = b - a + 1 - countDivBy(c,a,b) - countDivBy(d,a,b) + countDivBy(lcm,a,b)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, W = [int(i) for i in input().split()]
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = [int(i) for i in input().split()]
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)

### FIXED CODE ###

n, W = map(int, input().split())
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

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

while True:
    if abs(n-k)<n:
        n = abs(n-k)
    else:
        break
print(n)
        

### FIXED CODE ###

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

m = n % k
m1 = k - m

if m > m1:
  ans = m1
else:
  ans = m
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import sys
import time
input = sys.stdin.readline


def main():
    t1 = time.time()
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
            t2 = time.time()
            if t2 - t1 > 1.8:
                print('Yes')
                sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


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

def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in range(C)]  for i in range(R)]
    for i in range(R):
        for j in range(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in range(R):
        for j in range(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        
        time+=1
        new_black=set([])
        
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black.add((y1,y2))
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1
        new=[]
        new=new_black
        #print(new_black)
    return time    

H,W=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(H):
    A+=[input()]
grid=parse(A)
print(find(grid))
    
                    
                                
                    
                
            
            

        


### FIXED CODE ###

# Enter your code here. Read input from STDIN. Print output to STDOUT
def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in xrange(C)]  for i in xrange(R)]
    for i in xrange(R):
        for j in xrange(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in xrange(R):
        for j in xrange(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        
        time+=1
        new_black=set([])
        
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black.add((y1,y2))
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1
        new=[]
        new=new_black
        #print(new_black)
    return time    

H,W=list(map(int,raw_input().strip().split(' ')))
A=[]
for _ in xrange(H):
    A+=[raw_input()]
grid=parse(A)
print(find(grid))
### BUGGY CODE ###

n=int(input())
n=0
maxn=0
x = list(map(int, input().split()))
fx=[]
for i in range(0,len(x)):
    for j in range(i,len(x)-1):
        if x[j]>=x[j+1]:
            n+=1
        else:
            break
    if n>maxn:
        maxn=n
    n=0
print(maxn)
            
        


### FIXED CODE ###

n = int(input())
x = input().split()
y = [0]
c = 0
for i in range(n-1):
  if int(x[i]) >= int(x[i+1]):
    c = c + 1
  else:
    y.append(c)
    c = 0
y.append(c)
print(max(y))
### BUGGY CODE ###

N,X,Y = map(int,input().split(sep=" "))
root = []
X = X-1
Y = Y-1
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if j - i < abs(i-X)+abs(j-Y)+1:
            root.append(j-i)
        else:
            root.append(abs(i-X)+abs(j-Y)+1)
for k in range(1,N,1):
    print(root.count(k))
    root.count(k)

### FIXED CODE ###

N,X,Y = map(int,input().split(sep=" "))
root = []
X = X-1
Y = Y-1
sumRoot = [0 for i in range(0,N-1,1)]
for i in range(0,N,1):
    for j in range(i+1,N,1):
        if j - i < abs(i-X)+abs(j-Y)+1:
            sumRoot[j-i-1] += 1
        else:
            sumRoot[abs(i-X)+abs(j-Y)] += 1
for k in range(0,N-1,1):
    print(sumRoot[k])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
s=0
for i in range(n):
    s+=a[i]
for i in range(q):
    res=a.count(bc[i][0])
    s+=(bc[i][1]-bc[i][0])*res
    a=[bc[i][1] if ai==bc[i][0] else ai for ai in a]
    print(s)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
d=[0 for i in range(pow(10,5)+1)]
s=sum(a)
for i in range(n):
    d[a[i]]+=1
for i in range(q):
    s+=(bc[i][1]-bc[i][0])*d[bc[i][0]]
    print(s)
    d[bc[i][1]]+=d[bc[i][0]]
    d[bc[i][0]]=0
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]

for h in range(1, n+1):
    ans = 0
    memo = a.pop(h)    # 削除
    for i in range(n):
        ans += abs(a[i]-a[i+1])
    a.insert(h, memo)
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]
sa = 0
for i in range(n+1):
    sa += abs(a[i]-a[i+1])

for i in range(1, n+1):
    print(sa - (abs(a[i-1]-a[i]) + abs(a[i]-a[i+1])) + abs(a[i-1]-a[i+1]))
### BUGGY CODE ###

def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start, visited):
    if start in visited:
        return True
    
    stack = [(start, 0)]
    distance = []
    flag = True
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if label not in visited:
            tmp = graph.get(label, [])
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
        else:
            if flag and dis != visited[label]:
                flag = False
        #__logging(visited, stack)
    return flag

N, M = (int(i) for i in input().split())  

m_list = []
graph = {}

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    if L not in graph:
        graph[L] = [(R, D)]
        m_list.append(L)
    else:
        graph[L].append((R, D))
    if R not in graph:
        graph[R] = [(L, -1 * D)]
        m_list.append(R)
    else:
        graph[R].append((L, -1 * D))

visited = {}
flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###



def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True
    
    stack = [start]
    visited[start] = 0
    while stack:
        label = stack.pop()
        for nextnode, distance in graph[label]:
            if visited[nextnode] == -99999:
                stack.append(nextnode)
                visited[nextnode] = visited[label] + distance
            elif visited[nextnode] != visited[label] + distance:
                return False
    return True

N, M = (int(i) for i in input().split())  

graph = [[] for i in range(N+1)]

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    graph[L].append((R, D))
    graph[R].append((L, -1 * D))


visited = [-99999 for i in range(N+1)]

flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from copy import deepcopy
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res, length[i][j])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

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

import numpy as np
def serach(target, array):
    l, r = -1, len(array)
    while r - l > 1:
        m = (l+r)//2
        if array[m] < target:
            l = m
        else:
            r = m
    return l, r

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

BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
ret = 0
tmp = 0
for b, c in BC:
    l, r = serach(c, A[tmp:])
    if r <= 0:
        break
    b = min(b, r)
    ret += c * b
    tmp += b

print(sum(A[tmp:])+ret)

### FIXED CODE ###

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

total = 0
D = []
A = sorted(A, key=lambda x:x[1], reverse=True)
for b, c in A:
    if len(D) >= N:
        break
    D.extend([c]*b)
print(sum(D[:N]))