Harryxun/stf_run huggingface dataset:
s = input()
k = int(input())

array = []
for i in range(0, k):
    for j in range(0, len(s)-i):
        array.append(s[j:j+i+1])
print(sorted(set(array))[4])

### FIXED CODE ###

s = input()
k = int(input())

array = []
for i in range(0, k):
    for j in range(0, len(s)-i):
        array.append(s[j:j+i+1])

print(sorted(set(array))[k-1])
N,K = map(int,input().split())
x = list(map(int,input().split()))
xp = [i for i in x if i >= 0]
xn = [i for i in x if i < 0]
xn.reverse()
lp = len(xp)
ln = len(xn)
pc = min(K,lp)
pp = xp[pc-1]
if K>lp:
    nc = K-lp
    np = -xn[nc-1]
else:
    nc = 0
    np = 0
ans = pp + np + min(pp,np)
for i in range(pc):
    if nc == ln:
        break
    pp = xp[pc-i-2]
    np = -xn[nc]
    nc += 1
    ans = min(ans,pp + np + min(pp,np))
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
x = list(map(int,input().split()))
xp = [i for i in x if i >= 0]
xn = [i for i in x if i < 0]
xn.reverse()
lp = len(xp)
ln = len(xn)
if lp == 0:
    print(-xn[K-1])
    exit()
if ln == 0:
    print(xp[K-1])
    exit()
pc = min(K,lp)
pp = xp[pc-1]
if K>lp:
    nc = K-lp
    np = -xn[nc-1]
else:
    nc = 0
    np = 0
ans = pp + np + min(pp,np)
for i in range(pc-1):
    if nc == ln:
        break
    pp = xp[pc-i-2]
    np = -xn[nc]
    nc += 1
    ans = min(ans,pp + np + min(pp,np))
print(ans)
a = input
b = input
if a < b:
   print a '<' b
if a > b:
   print a '>' b
print a '==' b

### FIXED CODE ###

a, b = map(int, raw_input().split())

if a < b:
    print 'a < b'
elif a > b:
    print 'a > b'
else:
    print 'a == b'
r, c = map(int, input().split())
table = []
for i in range(r):
    table.append(list(map(int, input().split())))
for i in table:
    i.append(sum(i))
b = []
for i in range(c):
    b.append(sum(list(table[k for k in range(r)][i])))
b.append(sum(b))
for i in table:
    print(" ".join(map(str, i)))
print(" ".join(map(str, b)))


### FIXED CODE ###

r, c = map(int, input().split())
table = []
for i in range(r):
    table.append(list(map(int, input().split())))
for i in table:
    i.append(sum(i))
b = []
for i in range(c):
    x = 0
    for k in range(r):
        x += table[k][i]
    b.append(x)
b.append(sum(b))
for i in table:
    print(" ".join(map(str, i)))
print(" ".join(map(str, b)))
lstA = list(input())
lstB = list(input())
lstC = list(input())

maxA = len(lstA)
maxB = len(lstB)
maxC = len(lstB)

numA = 0
numB = 0
numC = 0

res = ''
tmp = 'a'



while True:
	if tmp == 'a':
		if numA == maxA:
			res = 'A'
			break
		tmp = lstA[numA]
		numA += 1

	elif tmp == 'b':
		if numB == maxB:
			res = 'B'
			break
		tmp = lstB[numB]
		numB += 1

	elif tmp == 'c':
		if numC == maxC:
			res = 'C'
			break
		tmp = lstC[numC]
		numC += 1

print(res)


### FIXED CODE ###

lstA = list(input())
lstB = list(input())
lstC = list(input())

maxA = len(lstA)
maxB = len(lstB)
maxC = len(lstC)

numA = 0
numB = 0
numC = 0

res = ''
tmp = 'a'

while True:
	if tmp == 'a':
		if numA == maxA:
			res = 'A'
			break
		tmp = lstA[numA]
		numA += 1

	elif tmp == 'b':
		if numB == maxB:
			res = 'B'
			break
		tmp = lstB[numB]
		numB += 1

	else:
		if numC == maxC:
			res = 'C'
			break
		tmp = lstC[numC]
		numC += 1

print(res)
n,k = input().split(' ')
n = int(n)
k = int(k)
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
diffs = []
for i in range(n-k+1):
    diffs = h[i+k] - h[i]
print(min(diffs))


### FIXED CODE ###

n,k = input().split(' ')
n = int(n)
k = int(k)
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
diffs = []
for i in range(n-k+1):
    diffs.append(h[i+k-1] - h[i])
print(min(diffs))
L, R = map(int, input().split())
if abs(L-R)>2019:
    print(0)
else:
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(ans, i*j%2019)
    print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if abs(L-R)>2019:
    print(0)
else:
    ans = 2019
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(ans, i*j%2019)
    print(ans)
x,a = int(input.split())
if x < a:
	print(0)
else:
	print(10)

### FIXED CODE ###

x, a = map(int,input().split())
if x < a:
	print(0)
else:
	print(10)
x  = (list[map(int,input().split()))
x = sum(x)
ans = 15-x
print(ans)
          

### FIXED CODE ###

x  = (list(map(int,input().split())))
x = sum(x)
ans = 15-x
print(ans)
import sys
import string

alphabets=list(string.ascii_lowercase)

s=input()

l=len(s)

hm = lambda a,string: sum([x==a for x in string])

for x in range(l-1):
  if s[x]==s[x+1]:
    print('{} {}'.format(x+1, x+2))
    sys.exit()

def func(r,s,n,m):
  if r==26:
    return print('-1 -1')
  else:
    if hm(alphabets[r],s[n:n+m])>m//2:
      print('{} {}'.format(r+1,n+m))
      sys.exit()
    return func(n+1,s,n,m)

for m in range(3,l,2):
  for n in range(l-m):
    func(0,s,n,m)

### FIXED CODE ###

import sys
import string
 
alphabets=list(string.ascii_lowercase)
 
s=input()
 
l=len(s)
 
hm = lambda a,string: sum([x==a for x in string])
 
for x in range(l-1):
  if s[x]==s[x+1]:
    print('{} {}'.format(x+1, x+2))
    sys.exit()
 
 
for n in range(l-3):
  for a in alphabets:
    if hm(a,s[n:n+3])> 1:
      print('{} {}'.format(n+1,n+3))
      sys.exit()
print('-1 -1')
A,B,K =map(int,input().split())
if A >= K:
  print(A-K,B)
elif B-(K-A) >= 0:
  print(0,B-(K-A))
else:
  print(0,0)

### FIXED CODE ###

s = list(map(str, input().split()))

print(s[1]+s[0])
N = input()

strList = list([])

for i in range(N):
  strList.append(str(input()))

strDict = {}

for item in strList:
  if item not in strDict.keys():
    strDict[item] = 1
  else:
    strDict[item] += 1

maxList = list([])

for strKeys in strDict.keys():
  if strDict[strKeys] == max(strDict.items()):
    maxList.append(strKeys)

print(maxList.sort())

### FIXED CODE ###

N = int(input())

strList = list([])

for i in range(N):
  strList.append(str(input()))

strDict = {}

for item in strList:
  if item not in strDict.keys():
    strDict[item] = 1
  else:
    strDict[item] += 1

maxList = list([])
maxNum = max(strDict.values())

for strKeys in strDict.keys():
  if strDict[strKeys] == maxNum:
    maxList.append(strKeys)

for srtedItem in sorted(maxList):
  print(srtedItem)
n=int(input())

s=input().split()

ans=[0 for i in range(n)]
for i in range(0,n-1):
    s[i]=int(s[i])
    ans[s[i]-1]+=1

for i in range(0,n):
    print(ans[i])




### FIXED CODE ###

n=int(input())

s=[0]*n

for i in range(0,n):
    s[i]=input()


s_set=set(s)
ans=len(s_set)
print(ans)
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]
CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

nums = [0, 1]
buy_or_not = list(itertools.product(nums, repeat=N))

knowledge_list = []
money_list = []

for bn in buy_or_not:
    knowledge = [0 for _ in range(M)]
    money = 0
    for i in range(M):
        if bn[i] == 1:
            money += CA[i][0]
            knowledge = [a + b for a, b in zip(knowledge, CA[i][1:])]

    knowledge_list.append(knowledge)
    money_list.append(money)

ans = INF

for i in range(len(money_list)):
    if min(knowledge_list[i]) >= X:
        ans = min(ans, money_list[i])

if ans != INF:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]

CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

knowledge_list = [[0 for _ in range(M)]]
money_list = [0]

for i in range(N):
    C = CA[i][0]
    A = CA[i][1:]

    # 購入する場合
    tmp2 = []
    for i, knowledge in enumerate(knowledge_list):
        tmp = []
        for k in range(len(knowledge)):
            tmp.append(knowledge[k] + A[k])
        
        tmp2.append(tmp)
        money_list.append(money_list[i]+C)

    knowledge_list = knowledge_list + tmp2

ans = INF
for i in range(len(money_list)):
    if min(knowledge_list[i]) >= X:
        ans = min(ans, money_list[i])

if ans != INF:
    print(ans)
else:
    print(-1)
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

int main() {
  int X,N; cin >>X >>N;
  if (N==0) {cout <<X <<endl; return 0;}
  vector<int> p(N);
  rep(i,0,N) cin >>p[i];
  sort(p.begin(),p.end());
  int ans=0;
  int check=INT_MAX;
  rep_eq(i,p[0],p[N-1]) {
    bool check_flag=true;
    rep(j,0,N) {
      if (i==p[j]) {check_flag=false; break;}
    }
    if (check_flag) {
      if (abs(X-i)<check) {check=abs(X-i); ans=i;}
    }
  }
  cout <<ans <<endl;
  return 0;
}


### FIXED CODE ###

X,N=map(int,input().split())
if N==0:
  print(X)
  exit()
p=list(map(int,input().split()))
ans=0
check=100
for i in range(101+1):
  if i in p:
    continue
  if abs(X-i)<check:
    check=abs(X-i)
    ans=i
print(ans)
N = int(input())
def convert(n,k):
    result = ""
    while n>0:
        result = al[(n%k)-1]+result
        n //= k
    return result
print(convert(N,26))

### FIXED CODE ###

n = int(input())
al=["z"]+[chr(ord('a') + i) for i in range(25)]
result = ""
while n>0:
    if n%26 !=0:
        result = al[n%26]+result
        n //= 26
    else:
        result = al[n%26]+result
        n //= 26
        n -= 1
print(result)
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = Integer.parseInt(sc.next());
    String s = sc.next();

    if(a>=3200){
      System.out.println(s);
    }
    else{
      System.out.println("red");
    }
  }
} 

### FIXED CODE ###

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

if n >= 3200:
  print(s)
else:
  print("red")
import collections
N = int(input())
s = [0]*N
countr = []
liss = []
for i in range(N):
  s[i] = input()
  a = collections.Counter(s[i])
  if a in liss:
    ind = liss.index(a)
    countr[ind] += 1
  else:
    liss.append(a)
    countr[len(liss)-1] = 1

ans = 0
for cc in countr:
  if cc > 1:
    ans = ans + cc * (cc - 1) / 2
print(ans)


### FIXED CODE ###

N = int(input())
liss = {}
for i in range(N):
  s = input()
  a = "".join(sorted(s))
  if a in liss:
    liss[a] += 1
  else:
    liss[a] = 1

ans = 0
for cc in liss:
  ans = ans + (liss[cc] * (liss[cc] - 1) / 2)
print(int(ans))
a,b,x = map(int,input().split())

print(b // x - a //x)

### FIXED CODE ###

A,B,C = map(str,input().split())
print("A"+B[0]+"C")
N = int(input())
if(N == 1):
  A1,B1 = map(int,input().split())
  print(str(A1+B1))
for i in range(N-1):
  if(i == 0):
    A1,B1 = map(int,input().split())
    A2,B2 = map(int,input().split())
    if(A1 <= A2):
      MA = A2
      MB = B2
    else:
      MA = A1
      MB = B1
    A1 = A2
    B1 = B2
  else:
    A2,B2 = map(int,input().split())
    if(MA <= A2):
      MA = A2
      MB = B2
    A1 = A2
    B1 = B2
print(str(MA + MB))

### FIXED CODE ###

N = int(input())
if(N == 1):
  A1,B1 = map(int,input().split())
  print(str(A1+B1))
  exit()
for i in range(N-1):
  if(i == 0):
    A1,B1 = map(int,input().split())
    A2,B2 = map(int,input().split())
    if(A1 <= A2):
      MA = A2
      MB = B2
    else:
      MA = A1
      MB = B1
    A1 = A2
    B1 = B2
  else:
    A2,B2 = map(int,input().split())
    if(MA <= A2):
      MA = A2
      MB = B2
    A1 = A2
    B1 = B2
print(str(MA + MB))
import sys


def solv(s):
    left, right = s.split('=')
    for i in range(10):
        l = left.replace('X', str(i))
        r = right.replace('X', str(i))
        if eval(l) == int(r):
            return str(i)
    else:
        return 'NA'


for line in sys.stdin:
    print solv(line.rstrip('\n'))

### FIXED CODE ###


import sys


def solv(s):
    for i in range(10):
        i = str(i)
        s2 = s.replace('X', i)
        left, right = s2.split('=')
        l1, l2 = left.split('+')
        if any([x[0] == '0' and len(x) > 1 for x in [l1, l2, right]]):
            continue
        if int(l1) + int(l2) == int(right):
            return i
    else:
        return 'NA'


for line in sys.stdin:
    print solv(line.rstrip('\n'))
N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if i * j == N:
            break
    if i * j == N:
        print("Yes")
        break
    elif i == 9 and i * j != N:
        print("No")

### FIXED CODE ###

A,B = map(int,input().split())
if A>=10 or B>=10:
   print(-1)
else:
   print(A*B)
import math
#from functools import reduce
a=int(input())
li=list(map(int,input().split()))
left_gcd=[]
left_gcd.append(li[0])
right_gcd=[]
right_gcd.append(li[a-1])

for i in range(a-1):
    left_gcd.append(math.gcd(left_gcd[i],li[i+1]))
k=0
for i in range(a-1,0,-1):
    right_gcd.append(math.gcd(right_gcd[k],li[i-1]))
    k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
num_li.append(right_gcd[a-2])
num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=math.gcd(left_gcd[(a-3)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))


### FIXED CODE ###

 
#from functools import reduce
def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x
 
a=int(input())
li=list(map(int,input().split()))
left_gcd=[0]
#left_gcd.append(li[0])
right_gcd=[0]
#right_gcd.append(li[a-1])

for i in range(a):
    left_gcd.append(gcd(li[i],left_gcd[i]))
    right_gcd.append(gcd(li[a-1-i],right_gcd[i]))
    #k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
#num_li.append(right_gcd[a-2])
#num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=gcd(left_gcd[(a-1)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))
import copy
n = input()
k = int(input())

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

dp = [[0] * 2 for _ in range(n_num)]
dp[0][0] = 1
for i in range(n_num):
    nxt = [[0] * 2 for _ in range(n_num + 1)]
    for j in range(n_num):
        for l in range(2):
            lim = 9 if l else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = l | (x < n_list[i])
                nxt[ns][nlt] += dp[j][l]
    dp = copy.deepcopy(nxt)
ans = dp[k][0] + dp[k][1]
print(ans)

### FIXED CODE ###

n = input()
k = int(input())

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

if n_num < k:
    print('0')
else:

    dp = [[[0] * (n_num + 1) for _ in range(2)]for _ in range(n_num + 1)]

    dp[0][0][0] = 1
    for i in range(n_num):
        for smaller in range(2):
            for j in range(n_num):
                lim = 9 if smaller else n_list[i]
                for x in range(lim + 1):
                    if x != 0:
                        ns = j + 1
                    else:
                        ns = j
                    nlt = smaller | (x < n_list[i])
                    dp[i + 1][nlt][ns] += dp[i][smaller][j]
    ans = dp[n_num][0][k] + dp[n_num][1][k]
    print(ans)
s = input()
k = int(input())
char = []
if len(s) == 1:
    print(s)
else:
    for i in range(len(s)):
        char.append(s[i])
    charset = set(char)
    ans = []
    for i in charset:
        for j in range(len(s)):
            if i == s[j]:
                for k in range(1, 6):
                    ans.append(s[j:j+k])
    ansset = sorted(list(set(ans)))
    print(ansset[k-1])

### FIXED CODE ###

s = input()
l = int(input())
char = []
if len(s) == 1:
    print(s)
else:
    for i in range(len(s)):
        char.append(s[i])
    charset = set(char)
    ans = []
    for i in charset:
        for j in range(len(s)):
            if i == s[j]:
                for k in range(1, 6):
                    ans.append(s[j:j+k])
    ansset = sorted(list(set(ans)))
    print(ansset[l-1])
n = int(input())
lst1 = list(range(1,n))
#lst2 = list(range(2,n+1))
#lst2.append(1)
#lst3 = list(range(2,n+1))
#del lst3[lst3.index(n//2+1)]
#lst3.append(n//2+1)
m_sum = sum(lst1)
#m_sum2 = sum(list(map(lambda x,y,:x%y, lst1, lst3)))
if n==1:
  print(0)
else:
  print(m_sum)

### FIXED CODE ###

n = int(input())
print(int(n*(n-1)//2))
import string

N = int(input())
alphabet = [chr(ord('a') + i) for i in range(26)]
num2alphabet = {i + 1: a for i, a in enumerate(alphabet)}

ans = ""

while N > 0:
    num = N % 26
    ans += num2alphabet[num]
    N = N // 26

print(''.join(list(reversed(ans))))


### FIXED CODE ###

import string

N = int(input())
alphabet = list(string.ascii_lowercase)
num2alphabet = {i + 1: a for i, a in enumerate(alphabet)}
num2alphabet[0] = "z"
ans = ""

while N > 0:
    num = N % 26
    ans += num2alphabet[num]
    if N <= 26:
        break

    if num == 0:
        N -= 1

    N = N // 26

print(''.join(list(reversed(ans))))
A, B = map(int, input().split())
print((A+B)%24)

### FIXED CODE ###

X = int(input())
A = int(input())
B = int(input())
print((X-A)%B)
from collections import defaultdict
import math


def f(n, k):
    base = 2 ** k
    syou = n // base
    amari = n % base
    q = max(0, amari - (base // 2) + 1)
    res1 = syou * (base // 2) + q
    return res1 % 2


def g(n):  # nを累計xorで表現
    keta = int(math.log2(n) + 1)
    s = ""
    for i in range(keta):
        s = str(f(n, i + 1)) + s
    return s


def xor(a, b):
    max_len = max(len(a), len(b))
    a = (("0" * max_len) + a)[-max_len:]
    b = (("0" * max_len) + b)[-max_len:]

    s = ""
    for i in range(max_len):
        if a[i] != b[i]:
            s += "1"
        else:
            s += "0"
    return s


def to10(s):
    res = 0
    for c in s:
        res *= 2
        if c == "1":
            res += 1
    return res


def main():
    n, m = [int(q) for q in input().split()]
    A = g(n - 1)
    B = g(m)
    res = xor(A, B)
    print(to10(res))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import math


def f(n, k):
    base = 2 ** k
    syou = n // base
    amari = n % base
    q = max(0, amari - (base // 2) + 1)
    res1 = syou * (base // 2) + q
    return res1 % 2


def g(n):  # nを累計xorで表現
    if n <= 0:
        return "0"
    keta = int(math.log2(n) + 1)
    s = ""
    for i in range(keta):
        s = str(f(n, i + 1)) + s
    return s


def xor(a, b):
    max_len = max(len(a), len(b))
    a = (("0" * max_len) + a)[-max_len:]
    b = (("0" * max_len) + b)[-max_len:]

    s = ""
    for i in range(max_len):
        if a[i] != b[i]:
            s += "1"
        else:
            s += "0"
    return s


def to10(s):
    res = 0
    for c in s:
        res *= 2
        if c == "1":
            res += 1
    return res


def main():
    n, m = [int(q) for q in input().split()]
    A = g(n - 1)
    B = g(m)
    res = xor(A, B)
    print(to10(res))


if __name__ == '__main__':
    main()
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>arr[temp] and temp<=n and i<m:
    ans+=mat[i][1]
    temp+=1
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        if i<m:
            maxboundary=mat[i][1]
    print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>arr[temp] and temp<n and i<m:
    ans+=mat[i][1]
    
    temp+=1
    if temp==n:
        break
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        if i<m:
            maxboundary=mat[i][1]
    #print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:51:01 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:54:27 +0900
#


import os
import sys
sys.setrecursionlimit(900000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()
a, b = input().split()

if 500*a >= b:
  print("Yes")
else:
  primt("No")

### FIXED CODE ###

a = list(map(int,input().split()))
 
if 500*a[0] >= a[1]:
  print("Yes")
else:
  print("No")