Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-

def func(n):
    if n==0:
        return 0 # 終端条件
    if memo[n] != -1:
        return memo[n] # 探索済み

    res = n

    for i in range(1,n+1):
        pow6 = 6 ** i
        if pow6 <= n:
            res = min(res, func(n-pow6)+1)
        else:
            break

    for i in range(1,n+1):
        pow9 = 9 ** i
        if pow9 <= n:
            res = min(res, func(n-pow9)+1)
        else:
            break

    memo[n] = res
    return res


N = int(input())

max_n = 110000
memo = [-1] * max_n
ans = func(N)
print(ans)


### FIXED CODE ###

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

def count(val1, val2):
    num = 1
    while True:
        if val1 < (val2 ** num):
            break
        num += 1

    cnt = 0
    digit = num
    while True:
        if val1 >= val2 ** digit:
            val1 -= val2 ** digit
            cnt += 1
        else:
            digit -= 1
        
        if digit== 0:
            break

    return cnt,val1


N = int(input())
ans = N

for i in range(0,N+1):
    n = i
    m = N - i
    res = 0

    cnt, nn = count(n, 9)
    n = nn
    res += cnt

    cnt, mm = count(m, 6)
    m = mm
    res += cnt

    res += n + m
    ans = min(ans, res)

print(ans)
n,k = map(int,input().split())
l_list = list(map(int,input().split()))
s_l_list = sorted(l_list,reverse = True)
ans_list = a_l_list[:k]
print(sum(ans_list))

### FIXED CODE ###

n,k = map(int,input().split())
l_list = list(map(int,input().split()))
s_l_list = sorted(l_list,reverse = True)
ans_list = s_l_list[:k]
print(sum(ans_list))
S = input()
K = int(input())
counter = 0
for i in S:
    if int(i) != 1:
        log = counter
        num = int(i)
        break
    counter += 1

if K == 1:
    print(S[0])
elif K <= log:
    print(1)
else:
    print(num)


### FIXED CODE ###

S = input()
K = int(input())
counter = 0
num = 1
log = 0
for i in S:
    if int(i) != 1:
        log = counter
        num = int(i)
        break
    counter += 1

if K <= log:
    print(1)
else:
    print(num)
abc=list(map(int,input().split()))
if max(abc)=abc[2]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

abc=list(map(int,input().split()))
if max(abc)==abc[0] and min(abc)==abc[1] or max(abc)==abc[1] and min(abc)==abc[0]:
  print("Yes")
else:
  print("No")
sss = input()
masu = list(sss)
counter = 0
if(masu[0] == 1):
    counter += 1
    elif (masu[1] == 1):
        counter += 1
    elif (masu[2] == 1):
        counter += 1
print(counter)

### FIXED CODE ###

sss = input()
masu = list(sss)
counter = 0
if(masu[0] == '1'):
    counter += 1
if (masu[1] == '1'):
    counter += 1
if (masu[2] == '1'):
    counter += 1
print(counter)
N = int(input())
A = list(map(int, input().split()))
rate = {"a":0, "b":0, "c":0, "d":0, "e":0, "f":0, "g":0, "h":0}
ratez = {"z":0}
for i in range(N):
    if A[i] >=1 and A[i] <= 399:
        rate["a"] += 1
    if A[i] >=400 and A[i] <= 799:
        rate["b"] += 1
    if A[i] >=800 and A[i] <= 1199:
        rate["c"] += 1
    if A[i] >=1200 and A[i] <= 1599:
        rate["d"] += 1
    if A[i] >=1600 and A[i] <= 1999:
        rate["e"] += 1
    if A[i] >=2000 and A[i] <= 2399:
        rate["f"] += 1
    if A[i] >=2400 and A[i] <= 2799:
        rate["g"] += 1
    if A[i] >=2800 and A[i] <= 3199:
        rate["h"] += 1
    if A[i] >=3200:
        ratez["z"] += 1
keys = [k for k, v in rate.items() if v != 0]

if ratez["z"] == 0:
    print(len(keys), len(keys))
elif len(keys) == 8:
    print(8, 8)
elif ratez["z"] <= len(keys) and len(keys) != 8:
    print(len(keys), len(keys)+ratez["z"])
elif ratez["z"] > len(keys) and len(keys) != 8 and ratez["z"] + len(keys) <= 8:
    print(rate["z"], len(keys)+ratez["z"])
elif ratez["z"] > len(keys) and len(keys) != 8 and ratez["z"] + len(keys) > 8 and ratez["z"] <= 8:
    print(rate["z"], 8)
elif ratez["z"] > len(keys) and len(keys) != 8 and ratez["z"] + len(keys) > 8 and ratez["z"] > 8:
    print(8, 8)

### FIXED CODE ###

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

cnt = [0] * 9
for i in a:
    x = min(i // 400, 8)
    if x >= 8:
        cnt[8] += 1
    else:
        cnt[x] = 1

if sum(cnt[:8]) == 0:
    l = 1
    r = cnt[8]
else:
    l = sum(cnt[:8])
    r = l+cnt[8]
print(l, r)
lis = list(input())
cou = 0
ans = 0
for i in range(len(lis)):
	if lis[i] == "g":
      if cou > 0:
        cou -= 1
        ans += 1
      else:
        cou += 1
    else:
      if cou > 0:
        cou -= 1
      else:
        cou += 1
        ans -= 1
print(max(0,ans))

### FIXED CODE ###

lis = list(input())
cou = 0
ans = 0
for i in range(len(lis)):
	if lis[i] == "g":
		if cou > 0:
			cou -= 1
			ans += 1
		else:
			cou += 1
	else:
		if cou > 0:
			cou -= 1
		else:
			cou += 1
			ans -= 1
print(max(0,ans))
a, b = [int(x) for x in input().rstrip("\n").split(" ")]
 
if b % a == 0:
  print(b + a)
else:
  print(b -ab)


### FIXED CODE ###

a, b = [int(x) for x in input().rstrip("\n").split(" ")]
 
if b % a == 0:
  print(b + a)
else:
  print(b - a)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

MOD = 10 ** 9 + 7

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

blue, red = K, N - K

p = 1 
d = 0

for i in range(1, blue + 1):
    print(int((comb(red + 1, p) * comb(blue - 1, d)) % MOD))
    p += 1
    d += 1



### FIXED CODE ###

def comb(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, K = map(int, input().split())

blue, red = K, N - K

p = 1 
d = 0

for i in range(1, blue + 1):
    print(int((comb(red + 1, p, mod) * comb(blue - 1, d, mod) % mod)))
    p += 1
    d += 1
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

dist = [None] * n
for i in range(n):
    dist[i], _ = dijkstra(n, edges, i)

q, k = map(int, input().split())
for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1][k-1] + dist[k-1][y-1])

### FIXED CODE ###

import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
import math
n=int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

f = factorization(n)
ans = 0
for i in f[1]:
    ans += int((-1+ math.sqrt(1+8*i))/2)
print(ans)

### FIXED CODE ###

n = int(input())

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

f = factorize(n)
ans = 0
for i,j in f:
    ans += int((-1+pow(1+8*j,0.5))/2)
print(ans)
from collections import Counter
import math
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = False
cnt = Counter()

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

plimes = get_primenumber(max(A))

def factorization(n):
    arr = []
    temp = n
    for p in plimes:
        if temp%p==0:
            while temp%p==0:
                temp //= p
            arr.append(p)
        if p > temp:
            break
    """
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    """
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, gcd, factorial
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, input().split())
    diff = abs(N - M)
    if diff > 1:
        print(0)
        return

    ans = 2 if diff == 0 else 1
    for i in range(1, N + 1):
        ans = (ans * i) % MOD
    for i in range(1, M + 1):
        ans = (ans * i) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, factorial
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, input().split())
    diff = abs(N - M)
    if diff > 1:
        print(0)
        return

    ans = 2 if diff == 0 else 1
    for i in range(1, N + 1):
        ans = (ans * i) % MOD
    for i in range(1, M + 1):
        ans = (ans * i) % MOD
    print(ans)


if __name__ == '__main__':
    main()
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy


N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    B,C=map(int, input().split())
    for _ in range(B):
        update.append(C)

update = sorted(update,reverse=True)

max_sum = sum(A)

for i in range(N):
    if i > len(update):
        break
    if(A[i] > update[i]):
        break
    A[i] = update[i]
    max_sum = max(max_sum, sum(A))

print(max_sum)

### FIXED CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
from time import time

N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    temp = list(map(int, input().split()))
    update.append(temp)

# C_i の値をkeyにしてソートする
update = sorted(update,key = lambda x:x[1], reverse=True)

idx = 0
for b, c in update:
    for i in range(b):
        if idx >= N:
            break
        if A[idx] < c:
            A[idx] = c
            idx += 1
        else:
            break

print(sum(A))
N = int(input())
S = str(input())

if N % 2 != 0:
  print('No')

wc = N / 2
wc1 = S[:wc]
wc2 = S[wc:]

if wc1 == wc2:
  print('Yes')

### FIXED CODE ###

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

if N % 2 == 0:
    T = S[:int(N/2)]
    if S == T + T:
        print('Yes')
    else:
      print('No')
else:
    print('No')
H,W = list(map(int, input().split(' '))
h,w = list(map(int, input().split(' '))
print((H-h)*(W-w))

### FIXED CODE ###

H,W = list(map(int, input().split(' ')))
h,w = list(map(int, input().split(' ')))
print((H-h)*(W-w))
n,k,q=map(int,input().split())
a=[k-q]*n
for i in range(q):
    point=int(input())
    a[point-1] += 1
for i in range(len(l)):
    if l[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

s =input()
ans = ["Sunny","Cloudy","Rainy"]
ans_index = (ans.index(s)+1)%3 -1
print(ans[ans_index+1])
n,k = map(int,input().split)

s = input().rstrip().split(' ')
a = int(s[0]) 
sorted = []
sorted.append(a)

for i in range(1,n):
  a = int(s[i]) 
  sorted.append(a)
  
  main = i
  sub = i-1
  while main = 0:
    if(sorted[sub] > sorted[main]):
      stock = sorted[sub]
      sorted[sub] = sorted[main]
      sorted[main] = stock
    else:
      break
     
    main -= 1
    sub -= 1

sum = 0
for j in range(0,k):
  sum += sorted[j]
  
print(sum)
    

### FIXED CODE ###

n,k = map(int,input().split())
 
s = input().rstrip().split(' ')
st = []
 
for i in range(0,n):
  a = int(s[i]) 
  st.append(a)
 
new_st = sorted(st)
sum = 0
for j in range(0,k):
  sum += new_st[j]
  
print(sum)
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        ONE+=tmp1
        ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    tmp1*=2
    tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)


### FIXED CODE ###

def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        if K>1:
            ONE+=tmp1
            ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    if K>1:
        tmp1*=2
        tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        if K==1:
            print(0)
            continue
        else:
            nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)
n,x = map(int,input().split())
lst = list(map(int, input().split()))

lst.append(x)
lst.sort()

dif_lst = []
for i in range(len(lst)-1):
    dif_lst.append(lst[i+1] - lst[i])
dif_lst.sort()

def dif_get(lst):
    dif_lst = [lst[0]]
    for i in range(len(lst)-1):
        dif = lst[i+1] - lst[i]
        if dif == 0:
            continue
        else:
            dif_lst.append(lst[i+1] - lst[i])
    dif_lst.sort()
    if dif_lst[0] == 1:
        return 1
    if len(dif_lst) == 1:
        return dif_lst[0]
    else:
        return dif_get(dif_lst)

print(dif_get(dif_lst))

### FIXED CODE ###

n,x = map(int,input().split())
lst = list(map(int, input().split()))
 
lst.append(x)
lst.sort()
 
dif_lst = []
for i in range(len(lst)-1):
    dif = lst[i+1] - lst[i]
    dif_lst.append(lst[i+1] - lst[i])
dif_lst.sort()

lst = dif_lst
while True:
    dif_lst = [lst[0]]
    for i in range(len(lst)-1):
        dif = lst[i+1] - lst[i]
        if dif == 0:
            continue
        else:
            dif_lst.append(lst[i+1] - lst[i])
    dif_lst.sort()
    if dif_lst[0] == 1:
        print(1)
        break
    elif len(dif_lst) == 1:
        print(dif_lst[0])
        break
    lst = dif_lst
s,t = list(input()),list(input())
s.sort()
t.sort(reverse=True)
count = 0
while count < len(s):
  if t[count] > s[count]:
    print("Yes")
    exit()
  else:
    count += 1
print("No")

### FIXED CODE ###

s = list(input())
s.sort()
s = "".join(s)

t = list(input())
t.sort(reverse=True)
t = "".join(t)

if s < t:
  print("Yes")
else:
  print("No")
import collections

s = list(input())
t = list(input())

cs = collections.Counter(s)
ct = collections.Counter(t)

slist = cs.values()
tlist = ct.values()

slist.sort()
tlist.sort()

if slist == tlist:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

import collections

s = list(input())
t = list(input())

cs = collections.Counter(s)
ct = collections.Counter(t)

slist = list(cs.values())
tlist = list(ct.values())

slist.sort()
tlist.sort()

if slist == tlist:
    print("Yes")
else:
    print("No")
#import time as time

#s = time.time()

n,m = map(int,input().split())
py = []
od = [[]*1 for i in range(n)]

#print ("create list: " + str(time.time() - s) )

#s = time.time()
for i in range(0,m):
    p,y = map(int,input().split())
    py.append([p,y])
       
    odlen = len(od[p-1])
    if odlen >= 1 :

        low = 0
        high = odlen - 1
        mid = odlen//2

        while low <= high:
            mid = (low + high) >> 1
            guess = od[p-1][mid]
            if guess == y:
                break
            if guess > y :
                high = mid - 1
            else:
                low  = mid + 1

        od[p-1].insert(low,y)

    else:
        od[p-1].append(y)

#print ("sort: " + str(time.time() - s) )

#s = time.time()
for i in range(0,m):
    r = od[py[i][0]-1].index(py[i][1])

    tmp = py[i][0]
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = tmp // 10
    
    for j in range(6-digit):
        print('0',end="")
    print(py[i][0],end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    for j in range(6-digit):
        print('0',end="")
    print(r+1)

#print ("index: " + str(time.time() - s) )

### FIXED CODE ###

x,y = map(int,input().split())
print(str(x+(y>>1)))
c1 = input()
c2 - input()

if c1[0]==c2[2] and c1[1]=c2[1] and c1[2]==c2[0] :
	print('YES')
	
else:
	print('NO')

### FIXED CODE ###

c1 = input()
c2 = input()

if c1[0]==c2[2] and c1[1]==c2[1] and c1[2]==c2[0] :
	print('YES')
	
else:
	print('NO')
S = input()
cha = list(S)
plist = []

for i in cha:
    if i == "B":
        del plist[-1]
    else:
        plist.append(i)

plist = "".join(plist)

print(plist)

### FIXED CODE ###

S = input()
cha = list(S)
plist = []

for i in cha: 
    if i == "B":
        if plist != []:
            del plist[-1]
    else:
        plist.append(i)
            
plist = "".join(plist)

print(plist)
A,B,C,D=[int(x) for x in input().rstrip().split()]
cnt=0

import math

def lcm(x, y):
  if x!=0 and y!=0:
    return (x * y) // math.gcd(x, y)
  else:
    return 0

    
baisuu=lcm(C,D)

u_A=(A-1)-(A-1)//C-(A-1)//D+(A-1)//baisuu

u_B=B-B//C-B//D+B//baisuu

print(u_B-u_A)

### FIXED CODE ###

import fractions
from functools import reduce

A,B,C,D=[int(x) for x in input().rstrip().split()]
cnt=0

import math

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

    
baisuu=lcm(C,D)

u_A=(A-1)-(A-1)//C-(A-1)//D+(A-1)//baisuu

u_B=B-B//C-B//D+B//baisuu

print(u_B-u_A)
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[0][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[i][j]:
      dpb[i+1][j] = True
      if j+wb < k:
        dpb[i+1][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[n-v-1]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)


### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
from bisect import bisect_right

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)

res = 0
for b, c in bc:
    if len(a) == 0:
        break
    count = bisect_right(a, c, hi=b)
    res += count * c
    a = a[count:]

print(res + sum(a))


### FIXED CODE ###

from bisect import bisect_right

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)

res = 0
fin = 0
for b, c in bc:
    count = bisect_right(a, c, lo=fin, hi=min(fin+b, len(a))) - fin
    fin += count
    res += count * c
for i in range(fin, len(a)):
    res += a[i]

print(res)