Harryxun/stf_run huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    
    def Warshall_Floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        return d
      
    n, m, l = map(int, input().split())
    f_inf = float('inf')
    dist = [[f_inf]*n for _ in range(n)]
    for i in range(m): dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    Warshall_Floyd(dist)

    dist2 = [[f_inf]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if dist[i][j] <= l:
                dist2[i][j] = 1
    
    Warshall_Floyd(dist2)

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if dist2[s-1][t-1] == f_inf:
            print(-1)
        else:
          ans = dist2[s-1][t-1]
          print(ans-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

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

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


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


if __name__ == "__main__":
    main()
import heapq

s=input()
k=int(input())
n=len(s)
ans=set()

for i in range(n):
    for j in range(1,n+1):
        ans.add(s[i:j])

ans.remove('')

ansh=[]
for ss in ans:
    heapq.heappush(ansh,ss)
    

for _ in range(k-1):
    heapq.heappop(ansh)
print(ansh[0])


### FIXED CODE ###

import heapq

s=input()
k=int(input())
n=len(s)
ans=set()

for i in range(n+1):
    j=1
    while j<=k and i+j<=n:
        ans.add(s[i:i+j])
        j+=1


ansh=[]
for ss in ans:
    heapq.heappush(ansh,ss)
for _ in range(k-1):
    heapq.heappop(ansh)
print(ansh[0])
len(set([int(input()) for _　in range(input())]))

### FIXED CODE ###

print(len(set([int(input()) for _ in range(int(input()))])))
while 1:
  try:
    a, b, c, d, e, f = map(float, raw_input().split())
    g = b / e
    x = (c - g * f) / a - g)
    y = (c - a * x) / b
    print str(x) + " " + str(y) + "\n"
  except:
    break

### FIXED CODE ###

while 1:
    try:
        a, b, c, d, e, f = map(float, raw_input().split())
        x = (c * e - b * f) / (a * e - b * d)
        y = (f * a - c * d) / (a * e - d * b)
        if x == -0.000:
            x = 0.000
        if y == -0.000:
            y = 0.000
        print str('%.3f' % x) + " " + str('%.3f' % y)
    except:
        break
n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    else if (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, x) == 0):
            count += 1
print(count)
 

### FIXED CODE ###

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    elif (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, x) == 1):
            count += 1
print(count)
import Decimal from decimal
a,b=map(Decimal,input().split())
print(int(a*b))

### FIXED CODE ###

from decimal import Decimal
a,b=map(Decimal,input().split())
print(int(a*b))
import sys
input = sys.stdin.readline

def dfs(v, p=-1):
    for u in to[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u, v)
    
def main():
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
        
    for i in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
        
    dfs(0)
    
    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    N, Q = map(int, input().split())
    to = [[] for i in range(N)]
    ans = [0] * N
    
    main()

### FIXED CODE ###

from collections import deque

def main():
  N, Q = map(int, input().split())
  visited = [False] * (N+1)
  graph = {i:deque() for i in range(N+1)}

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

  visited[1] = True

  c = [0] * (N+1)
  for i in range(Q):
    p, x = map(int, input().split())
    c[p] += x
    
  q = [1]
  while q:
    per = q.pop()
    for child in graph[per]:
      if not visited[child]:
        visited[child] = True
        c[child] += c[per]
        q.append(child)

  for i in range(1, N+1):
    print(c[i], '', end='')

if __name__ == '__main__':
  main()
a = raw_input()
b = raw_input()
a = str(a)
b = str(b)
length = len(a)
if a == b[0:length]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a = input()
b = input()
a = str(a)
b = str(b)
length = len(a)
if a == b[0:length]:
    print("Yes")
else:
    print("No")
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
avail = [True for _ in range(len(A))]

count = 0
for i in range(len(A) - 1, -1, -1):
    if not avail[i]:
        continue
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    while True:
        if A[j] != comp:
            break
        if i == j or not avail[j]:
            j += 1
            continue
        avail[i] = False
        avail[j] = False
        count += 1
        break

print(count)


### FIXED CODE ###

# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
B = []
C = []
i = 0
while i < len(A):
    j = i
    count = 1
    while i+1 < len(A) and A[j] == A[i+1]:
        count += 1
        i += 1
    B.append(A[j])
    C.append(count)
    i += 1

count = 0
i = len(B) - 1
while i >= 0:
    comp = getComp(B[i])
    j = bisect_left(B, comp)
    if i == j and C[i] < 2:
        i -= 1
        continue
    if B[j] != comp:
        i -= 1
        continue
    if not C[i] or not C[j]:
        i -= 1
        continue
    C[i] -= 1
    C[j] -= 1
    count += 1

print(count)
S=int(input())

h=S/3600

m=S%3600/60

s=S%3600%60

print(":"join( h,m,s))

### FIXED CODE ###

S=int(input())
 
h=S//3600
 
m=(S%3600)//60
 
s=(S%3600)%60
 
print('{0}:{1}:{2}'.format(h,m,s))
i = 1
x = int(input())
for y in x:
    if y == 0:
        break
    print(f 'Case {i}: {y}')
    i += 1



### FIXED CODE ###

case_num = 1

while True:
    tmp_num = int(input())
    if tmp_num == 0:
        break
    else:
        print("Case %d: %d" % (case_num,tmp_num))
        case_num += 1
K, X = [int(n) for n in input().split()]
print(" ".join([n for n in range(X-(K-1), X+(K-1))]))

### FIXED CODE ###

K, X = [int(n) for n in input().split()]
print(" ".join([str(n) for n in range(X-(K-1), X+(K))]))
import numpy as np
A, B, N, = map(int, input().split())
def f(x):
    global A, B
    return np.floor(A*x/B)-A*np.floor(x/B)
print(int(np.max(f(np.arange(N+1)))))

### FIXED CODE ###

from math import floor
A, B, N = map(int, input().split())
print(floor(A*min(B-1, N)/B))
x = input()
 print(int(x)*int(x)*int(x))

### FIXED CODE ###

x = input()
ans = x**3
print ans
s = str(input())
l = [MON, TUE, WED, WED, THU, FRI, SAT, SUN]

if s == "SUN":
  print(7)
else:
  for i in range(7):
    if s == l[i]
       print(i)


### FIXED CODE ###

s=input()
l=['SUN','MON','TUE','WED','THU','FRI','SAT']
for i in range(7):
  if s==l[i]:print(7-i)
rc = list(map(int, input().split()))

digit = 1
while src[1] ** digit - 1 < src[0]:
    digit += 1

print(digit)

### FIXED CODE ###

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

digit = 1
while src[1] ** digit - 1 < src[0]:
    digit += 1

print(digit)
numbers = list(map(int, input().split()))
k = int(input())
sum = 0
for i in range(3):
  if i == numbers.index(max(numbers)):
    sum += max(numbers) * (2 ^ k) 
  else:
    sum += numbers[i]
print(sum)

### FIXED CODE ###

a, b = map(int,input().split())
if a <= b:
  print(a)
elif a > b:
  print(a-1)
a,b,x = map(int, input().split())

import math
def digit(n):
  return math.floor(math.log(n,10))+1
  
n_max = 10**9
n_min = 0

while((n_max-n_min)>1):
  key = (n_max+n_min)//2
  if a*key + b*digit(key) < x:
    n_min = key
  elif a*key + b*digit(key) > x:
    n_max = key

if n_max*a + b*digit(n_max) < x:
  print(n_max)
else:
  print(n_min)



### FIXED CODE ###

s = input()

dic = {'SUN':7,'MON':1,'TUE':2,'WED':3,'THU':4,'FRI':5,'SAT':6}

if s == 'SUN':
  print(7)
else:
  print(dic['SUN']-dic[s])
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.append(n)
  return divisors
n,x=map(int,input().split())
y=list(map(int,input().split()))
y.append(x)
y.sort()
z=[]
for i in range(n-1):
  z.append(y[i+1]-y[i])
z.sort()
p=make_divisors(z[0])
a=[]
for i in p:
  for j in z:
    if j%i:
      break
  else:
    a.append(i)
print(max(a))

### FIXED CODE ###

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.append(n)
  return divisors
n,x=map(int,input().split())
y=list(map(int,input().split()))
y.append(x)
y.sort()
z=[]
for i in range(n):
  z.append(y[i+1]-y[i])
z.sort()
p=make_divisors(z[0])
a=[]
for i in p:
  for j in z:
    if j%i:
      break
  else:
    a.append(i)
print(max(a))
a,b=map(int,input().split())
if a+b≧24:
    print(a+b-24)
else:
    print(a+b)

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b>=24):
    print(a+b-24)
else:
    print(a+b)
# -*- coding: utf-8 -*-
from itertools import product

H, W , K = [int(i) for i in input().split()]
c = [list(input()) for _ in range(h)]
ans = 0

for row_bit in product(range(2),repeat=H):
    for col_bit in product(range(2),repeat=W):
        cnt = 0
        for row in range(H):
            for col in range(W):
                if c[row][col] = "#" and  (row_bit[row] and col_bit[col]):
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import itertools
from copy import deepcopy

H, W , K = [int(i) for i in input().split()]

Arr = np.zeros((H, W))
for i in range(H):
    words = input()
    for j, w in enumerate(words):
        if w == "#":
            Arr[i,j] = 1
#print(Arr)
ans = 0
for t in range(0,H+W):
    Ex = list(itertools.combinations([int(i) for i in range(H+W)],t))
    for j in Ex:
        TMP = deepcopy(Arr)
        for num in j:
            if num < H:
                TMP[num] = np.zeros(W)
            else:
                w = num - H
                #print(TMP)
                TMP[:,w] = np.zeros(H)
                #print(w,TMP[:,w])
        if K == int(np.sum(TMP)):
            ans += 1
print(ans)
h, w=map(int, input().split())
# 偶数と奇数で場合分け
if h%2==0:
  # 1列でh/2個のマスできるからあとは横何個あるかだけ
  print(int(h*w/2))
else:
  set1=h
  if w%2==0:
    print(int(set1*w/2))
  else:
    rm=w//2
    print(int(set1*rm+h//2+1))

### FIXED CODE ###

n=int(input())
a=int(n/1.08)
aa=a-1
aaa=a+1
b=int(a*1.08)
bb=int(aa*1.08)
bbb=int(aaa*1.08)
A=[a,aa,aaa]
B=[b,bb,bbb]
f=0
for i in range(3):
  if B[i]==n:
    f=1
    ans=A[i]
    break
if f==0:
  print(":(")
else:
  print(ans)
nums = input()
S = int(nums.split(' ')[0])
W = int(nums.split(' ')[1])

if W >= S:
	print(unsafe)
else:
	print('safe')

### FIXED CODE ###

nums = input()
S = int(nums.split(' ')[0])
W = int(nums.split(' ')[1])

if W >= S:
	print('unsafe')
else:
	print('safe')
a,b = map(int,input())
point = 0
point += max(a,b)

if max(a,b) == a:
  point += max(a-1,b)
  print(point)
else:
  point += max(a,b-1)
  print(point)

### FIXED CODE ###

a,b = map(int,input().split())
point = 0
point += max(a,b)

if max(a,b) == a:
  point += max(a-1,b)
  print(point)
else:
  point += max(a,b-1)
  print(point)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))[::-1]
    ind = [-1] * (n + 1)
    for i in range(n):
        if i == 0:
            ind[b[i]] = 0
        elif b[i] != b[i - 1]:
            ind[b[i]] = i
    for i in range(n):
        if a[i] != b[i]:
            continue
        else:
            swap = 0
            for j in range(b[i] - 1, 0, -1):
                if ind[j] != -1 or ind[j] >= ind[j - 1]:
                    swap = ind[j]
                    ind[j] += 1
                    break
            b[i], b[swap] = b[swap], b[i]
    if all(a[i] != b[i] for i in range(n)):
        print("Yes")
        print(" ".join(map(str, b)))
    else:
        print("No")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def solve(n):
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))[::-1]
    ind = [-1] * (n + 1)
    for i in range(n):
        if i == 0:
            ind[b[i]] = 0
        elif b[i] != b[i - 1]:
            ind[b[i]] = i
    cnt = 0
    for i in range(n):
        if a[i] != b[i]:
            continue
        else:
            swap = 0
            for j in range(b[i] - 1, 0, -1):
                if ind[j] != -1 or ind[j] >= ind[j - 1]:
                    swap = ind[j]
                    ind[j] += 1
                    break
            if n <= swap:
                swap = cnt
                cnt += 1
                cnt %= n
            b[i], b[swap] = b[swap], b[i]
    return a, b


def main():
    n = int(input())
    a, b = solve(n)
    if all(a[i] != b[i] for i in range(n)):
        print("Yes")
        print(" ".join(map(str, b)))
    else:
        print("No")


if __name__ == '__main__':
    main()
s = []
while 1:
 inp = input().lower()
 if inp == EOF:
  break
 s.append(inp)
for i in range(ord('a'), ord('z')+1):
 print("{0} : {1}".format(chr(i), s.count(chr(i))))

### FIXED CODE ###

import sys 
dataset = sys.stdin.readlines()

for s in range(ord('a'), ord('z') + 1):
 count = 0
 for data in dataset:
  count += data.lower().count(chr(s))
 print("{0} : {1}".format(chr(s), count))
# -*- coding: utf-8 -*-

S = input()
T = input()

if S in T == True:
    if T[len(T)-1] == S[len(S)-1]
    print('Yes')
else:
    print('No')

### FIXED CODE ###

# -*- coding: utf-8 -*-

S = input()
T = input()
l = len(S)

for i in range(0,l):
    if S[i] == T[i]:
        i = i + 1
        if i == l:
            print('Yes')
            break
    else:
        print('No')
        break
h,w = (int(i) for i in input().split())
M = [input() for i in range(h)]
N = [[False]*w for i in range(h)]
print(M)
cnt = 0
for i in range(h):
    for j in range(w):
        if M[i][j] == "#":
            cnt += 1
print(cnt)
ans = 0
def dfs(x,y):
    global ans
    if M[x][y] == "#":
        return
    elif N[x][y]:
        return
    elif x == w-1 and y == h-1:
        print(h*w-(ans+1+cnt))
        exit()
    else:
        N[x][y] = True
        ans += 1
        A = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
        for a in A:
            if 0<=a[0]<=w-1 and 0<=a[1]<=h-1:
                dfs(a[0],a[1])

dfs(0,0)
print(-1)

### FIXED CODE ###

from collections import deque
h,w = (int(i) for i in input().split())

M = [input() for i in range(h)]
N = [[False]*w for i in range(h)]

cnt = 0
for i in range(h):
    for j in range(w):
        if M[i][j] == "#":
            cnt += 1


que = deque([[0,0,1]])
while que:
    x,y,c = que.popleft()

    if M[y][x] == "#":
        continue
    elif N[y][x]:
        continue
    elif x == w-1 and y == h-1:
        
        print(h*w-(c+cnt))
        quit()

    else:
        N[y][x]=True
        A = [[x+1,y,c+1],[x-1,y,c+1],[x,y+1,c+1],[x,y-1,c+1]]
        for a in A:
            if 0<=a[0]<=w-1 and 0<=a[1]<=h-1:
                que.append(a)
                
print(-1)
N = int(input())
A = sorted(list(map(int, input().split())))

for i in range N-1
	A[i+1] = A[i] + A[i+1]

 print(A[N-1])

### FIXED CODE ###

n = int(input())
v = sorted(list(map(int, input().split())))

for i in range(n - 1):
    v[i + 1] = (v[i] + v[i + 1]) / 2

print(v[n - 1])
n = int(input())
if !n%2:
    n += 1

result = 0

for i in range(1,n+2,2):
    cnt = 0

    for ii in range(1,i+2,2):
        if i%ii == 0:
            cnt += 1

    if cnt >= 8:
        result += 1

print(result)

### FIXED CODE ###

n = int(input())
if not n%2:
    n -= 1

result = 0

for i in range(1,n+2,2):
    cnt = 0

    for ii in range(1,i+2,2):
        if i%ii == 0:
            cnt += 1

    if cnt >= 8:
        result += 1

print(result)
from math import *
from collections import *
from itertools import *
from bisect import *
from operator import *
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
def o():
    return int(input())
def kl(con,x=0):
    if x==0:print('Yes') if con else print('No')
    elif x==1:print('yes') if con else print('no')
    elif x==2:print('YES') if con else print('NO')

MOD =    1000000007
MAX=2147483647
MIN=-2147483648
p=input
l,l1,l2,l3=[],[],[],[]
# for _ in range(o()):
n,k=io()
l=op()
x=y=0
i=0
fr=[0]*(2*(10**5))
while 1:
    if fr[l[i]]==0:
        l1.append(l[i])
        fr[l[i]]=1
        i=l[i]-1
    else:
        y=l1.index(l[i])
        x=len(l1)-y
        break
if k<=len(l1):
    print(l1[k-1])
else:
    k-=y
    k%=x
    print(l1[y+k-1])

### FIXED CODE ###

from math import *
from collections import *
from itertools import *
from bisect import *
from operator import *
import sys
sys.setrecursionlimit(1000000)
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
def o():
    return int(input())
def kl(con,x=0):
    if x==0:print('Yes') if con else print('No')
    elif x==1:print('yes') if con else print('no')
    elif x==2:print('YES') if con else print('NO')

MOD =    1000000007
MAX=2147483647
MIN=-2147483648
p=input
l,l1,l2,l3=[],[],[],[]
# for _ in range(o()):
n,k=io()
l=op()
x=y=0
i=0
fr=[0]*(200002)
while 1:
    if fr[l[i]]==0:
        l1.append(l[i])
        fr[l[i]]=1
        i=l[i]-1
    else:
        y=l1.index(l[i])
        x=len(l1)-y
        break
if k<=len(l1):
    print(l1[k-1])
else:
    k-=y
    k%=x
    if k==0:
        k=x
    print(l1[y+k-1])
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

n, m = map(int, rl().split())
li = [[] for _ in range(m)]
for _ in range(m):
  a, b = map(int, rl().split())
  a -= 1
  b -= 1
  li[a].append(b)
  li[b].append(a)

marks = [-1]*n
marks[0] = 0
def dfs(aa, x):
  marks[x] = aa
  for nr in li[x]:
    if marks[nr] == -1:
      dfs(x, nr)
  
  
dfs(0, 0)
if -1 in marks:
  print('No')
else:
  print('Yes')
  for i in marks[1:]:
    print(i+1)


### FIXED CODE ###

import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

n, m = map(int, rl().split())
li = [[] for _ in range(m+1)]
for _ in range(m):
  a, b = map(int, rl().split())
  a -= 1
  b -= 1
  li[a].append(b)
  li[b].append(a)

marks = [-1]*n
stack = [0]
while stack:
    for next_room in li[stack[0]]:
        if marks[next_room] == -1:
            stack.append(next_room)
            marks[next_room] = stack[0]
    del stack[0]
if -1 in marks:
  print('No')
else:
  print('Yes')
  for i in marks[1:]:
    print(i+1)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
n = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

data = {}

tmp = 0
for i in range(N):
  tmp += a[i]
  if tmp%M not in data:
    data[tmp%M] = 1
  else:
    data[tmp%M] += 1
else:
  data[0] += 1

cnt = list(data.values())
ans = 0
for i in cnt:
  if i == 1:
    continue
  else:
    ans += cmb(i,2,mod)
print(ans)

### FIXED CODE ###

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

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

S = {0 : 1}
t = 0
for i in range(N):
  t = (t + D[i]) % M
  if t in S:
    S[t] += 1
  else:
    S[t] = 1

r = 0

for i in S.values():
  r += i * (i - 1) // 2
  
print(r)
n,m = map(int,input().split())
A = list(map(int,input().split()))
tehuda = []
for i in range(m):
    b,c = map(int,input().split())
    tehuda.append((b,c))
# とりあえず和
sumA = sum(A)
import heapq
heapq.heapify(A)
tehuda = sorted(tehuda,key = lambda x:x[1])
#print(tehuda)
over = True
while tehuda:
    if not over:
        break
    b,c = tehuda.pop()
    while True:
        m = heapq.heappop(A)
        #print(m,c)
        if m >= c:
            over = False
            break
        else:
            b -= 1
            #print(sumA)
            sumA -= m
            #print(sumA)
            sumA += c
            #print(sumA)
            if b == 0:
                break
print(sumA)


### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
tehuda = []
for i in range(m):
    b,c = map(int,input().split())
    tehuda.append((b,c))
# とりあえず和
sumA = sum(A)
import heapq
heapq.heapify(A)
tehuda = sorted(tehuda,key = lambda x:x[1])
#print(tehuda)
over = True
while tehuda:
    if not over:
        break
    b,c = tehuda.pop()
    while True:
        m = heapq.heappop(A)
        #print(m,c)
        if m >= c:
            over = False
            break
        else:
            b -= 1
            sumA -= m
            sumA += c
            heapq.heappush(A,c)
            if b == 0:
                break
print(sumA)
import sys
input = sys.stdin.readline

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))


### FIXED CODE ###

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))
num=[]
for i in [0]*2:
    num.append(int(input()))
if num[0]>num[1]:
    print("GREATER")
elif num[0]=num[1]:
    print("EQUAL")
else:
    print("LESS")

### FIXED CODE ###

num=[]
for i in [0]*2:
    num.append(int(input()))
if num[0]>num[1]:
    print("GREATER")
elif num[0]==num[1]:
    print("EQUAL")
else:
    print("LESS")