Harryxun/stf_run huggingface dataset:
#A = 初期値　B = 一日の購入　C = 乳化のボーダー　D =在庫の増やす数

#A > B
#D % B >= B - C

size = int(input())
data = []
flag = 0

for i in range(size):
    ip = input().split()
    data = []
    for j in ip:
        data.append(int(j))
    #定義
    buf = []
#    print(store,buy,bord,charge,buf)
    #最初の処理
    data[0] = data[0] % data[1]
    if data[0] > data[3]:
        flag = 1
    #定常処理
    while data[0] not in buf:
        buf.append(data[0])
        data[0] = (data[0] + data[3]) % data[1]
        if data[0] > data[3]:
            flag = 1
            break
 #   print(buf)
    if flag == 1:
        print("No")
        flag = 0
    else:
        print("Yes")


### FIXED CODE ###

input()
ip = input().split()
data = []
for i in ip:
    data.append(int(i))

buf = -1
enc = 0
for i in data:
    if buf == i:
        enc += 1
        buf = -1
    else:
        buf = i

print(enc)
# AOJ 2805: Tournament
# Python3 2018.7.11 bal4u

def calc(l, n):
	if n == 2:
		if a[l] and a[l+1]: return [0, True]
		if a[l] or a[l+1]: return [0, False]
		return [1, False]
	m = n >> 1
	c1, f1 = calc(l, m)
	c2, f2 = calc(l+m, m)
	if f1 and f2: return [c1+c2, True]
	if f1 or f2: return [c1+c2, False]
	return [c1+c2+1, False]

while True:
	N, M = map(int, input().split())
	if M == 0: print(N-1)
	else:
		a = [False]*256
		for i in range(M): a[int(input())] = True
		print(calc(0, N)[0])


### FIXED CODE ###

# AOJ 2805: Tournament
# Python3 2018.7.11 bal4u

N, M = map(int, input().split())
print(N-1-M)
from math import factorial as fact
from collections import Counter

N = int( input() )
tree = list( map( int, input().split() ) )
ans = 1
if tree[0] != 0:
    print(0)
else:
    c = Counter(tree)
    if c[0] != 1:
        print(0)
    else:
        a = 1
        for i in range( 1,len(c)):
            t = c[i]
            if a == 1:
                ans *= t
            else:
                ans *= int( a ** t / fact(a) )
            a = t 
        print(ans)


### FIXED CODE ###

from math import factorial as fact
from collections import Counter
import sys

N = int( input() )
tree = list( map( int, input().split() ) )
ans = 1
if tree[0] != 0:
    print(0)
else:
    c = Counter(tree)
    if c[0] != 1:
        print(0)
    else:
        ans = 1
        a = c[0]
        for i in range( 1,len(c)):
            t = c[i]
            if t == 0:
                print(0)
                sys.exit()
            else:
                ans *= ( a**t )
                a = t
        print(ans%998244353)
from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))
A = list(accumulate(A))
ans = []

for i in range(N-3):
    for j in range(i+1, N-2):
        for k in range(j+1, N-1):
            list = []
            p = A[i]
            q = A[j]-A[i]
            r = A[k]-A[j]
            s = A[-1]-A[k]
            list = [p, q, r, s]
            ans.append(max(list) - min(list))

print(min(ans))


### FIXED CODE ###

N = int(input())
if N % 2 == 0:
    print(N)
else:
    print(2 * N)
a = input()
b = []

for s in a:
  if s=="0" or s=="1":
    b.append(s)
  else:
    b.pop()
else:
  print("".join(b))

### FIXED CODE ###

a = input()
b = []

for s in a:
  if s=="0" or s=="1":
    b.append(s)
  elif s=="B" and len(b)!=0:
    b.pop()
else:
  print("".join(b))
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>2][j]
        else:
            dp[i][j] = max(dp[i>>2][j], dp[i>>2][j - w] + v)

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
S = list(input())

P = set(S)

flag = 0
if len(S) == 26:
    Q = set()
    for i in range(25):
        if ord(S[25 - i]) < ord(S[25 - i - 1]):
            Q.add(ord(S[25 - i]))
            S.pop()
        else:
            while len(Q)>0 and ord(S[25 - i - 1])>min(Q):
                Q.remove(min(Q))
            S.pop()
            S.pop()
            S.append(chr(min(Q)))
            flag = 1
            break
else:
    for j in range(26):
        M = chr(97 + j)
        if M in P:
            pass
        else:
            S.append(M)
            flag = 1
            break

if flag == 0:
    print(-1)
else:
    print(''.join(S))

### FIXED CODE ###

S = list(input())

P = set(S)

flag = 0
if len(S) == 26:
    Q = set()
    for i in range(25):
        if ord(S[25 - i]) < ord(S[25 - i - 1]):
            Q.add(ord(S[25 - i]))
            S.pop()
        else:
            while len(Q)>0 and ord(S[25 - i - 1])>min(Q):
                Q.remove(min(Q))
            if len(Q)>0:
                S.pop()
                S.pop()
                S.append(chr(min(Q)))
                flag = 1
                break
            else:
                Z = S[25-i]
                S.pop()
                S.pop()
                S.append(Z)
                flag = 1
                break
else:
    for j in range(26):
        M = chr(97 + j)
        if M in P:
            pass
        else:
            S.append(M)
            flag = 1
            break

if flag == 0:
    print(-1)
else:
    print(''.join(S))
n = input()
d = list(map(int,input().split()))
d.sort()
print(d[int(n / 2)] - d[int(n/2) -1])


### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
print(d[int(n / 2)] - d[int(n/2) -1])
n = int(input())
b = list(input().split())
c = list(input().split())
r=0
for i in range(n):
  if b[i]-c[i]>0:
    r = r + b[i] - c[i]
    
print(r)

### FIXED CODE ###

n = int(input())
b = list(map(int,input().split()))
c = list(map(int,input().split()))
r=0
for i in range(n):
  if b[i]-c[i]>0:
    r = r + b[i] - c[i]
    
print(r)
li = list(map(int,input().split()))

S1 = min(l1[0] * li[3], l1[0] * (li[1] - li[3]))
S2 = min(li[2] * li[1], (li[0] - li[2]) * li[1])

if S1 == S2:
    print(S1, 1)
else:
    print(min(S1, S2), 0)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    s = list(map(int,input().split()))

    if (s[0] / 2.0 == s[2]) and (s[1] / 2.0 == s[3]):
        print(s[0] * s[1] / 2.0, 1)
    else:
        print(s[0] * s[1] / 2.0, 0)

if __name__ == '__main__':
    main()
def next_array(array):#辞書式に次の配列を与える関数
	s = -1
	for x in array[::-1]:
    	if x < M:
        	break
        else:
        	s -= 1
    #Mより小さい最後の項を取得
    
    if s >= -N:
      array[s] += 1#その項を１増やす
      if s < -1:
      	for i in range(s+1,0)#以降の項を全て同じ値に
      		array[i] = array[s]
        
	return array
 
def score(array, rules):#点数計算
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ

### FIXED CODE ###

def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]

  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)
num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = ""
while 1:
    for Ai in A:
        if dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break
    if remain_match == 0:
        break
print(int(ans))


### FIXED CODE ###

num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = "0"
while remain_match > 0:
    for Ai in A:
        if remain_match >= num_A[Ai] and dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans[1:]))
n,k=map(int,input().split())
h=list(map(int,input().split()))
count=0
for i in h:
    if k<=i:
        count+=1
print(count)

### FIXED CODE ###

n=int(input())
if n%2==0:
    print(1/2)
else:
    print((int(n/2)+1)/n)
n = int(input())
w = list(map(int,input(),split()))
ans = 1000000000
for t in range(1, n);
    left = sum(w[:t])
    right = sum(w[t:])
    ans = min(ans , abs(left - right))
print(ans)
        

### FIXED CODE ###

n = int(input())
w = list(map(int,input().split()))
ans = 1000000000
for t in range(1, n):
    left = sum(w[:t])
    right = sum(w[t:])
    ans = min(ans , abs(left - right))
print(ans)
from sys import stdin
data=[int(x) for x in stdin.readline().rstrip().split()]
data=sorted(data)
print(abs(data[0]-data[-1])

### FIXED CODE ###

from sys import stdin
N=int(stdin.readline().rstrip())
data=[int(x) for x in stdin.readline().rstrip().split()]
data=sorted(data)
print(abs(data[0]-data[-1]))
#include<stdio.h>
int max(int a,int b){
    int h=a;
    if(b>a)h=b;
    return h;
}
int set(int n,int w[],int v[],int W){
    if(n==0){
        return 0;
    }else if(w[n-1]>W){
        return set(n-1,w,v,W);
    }else{
        return max(set(n-1,w,v,W),set(n-1,w,v,W-w[n-1])+v[n-1]);
    }
}
int main(void){
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N],w[N];
    for(int i=0;i<N;i++){
        scanf("%d%d",&v[i],&w[i]);
    }
    printf("%d\n",set(N,w,v,W));
    return 0;
}


### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0 for i in range(W+1)]
dp=np.array(dp)
for i in range(N):
    dp[w[i]:]=np.maximum(dp[w[i]:],dp[:W-w[i]+1]+v[i])
print(dp.max())
s = list(input())

ans = []
for i in range(0,len(s)-2):
  d = int("".join(s[i]+s[i+1]+s[i+2]))
  ans.append(abs(b-753))
  
print(min(ans))

### FIXED CODE ###

s = list(input())

ans = []
for i in range(0,len(s)-2):
  d = int("".join(s[i]+s[i+1]+s[i+2]))
  ans.append(abs(d-753))
  
print(min(ans))
n=int(input())
c=[0]*n;s=[0]*n;f=[0]*n
for i in range(n):
  c[i],s[i],f[i]=map(int,input().split())
  
for i in range(n):
  ans=0
  for j in range(i,n):
    ans+=c[i]+(s[i]+f[i]-ans)%f[i]
  print(ans)
    

### FIXED CODE ###

n=int(input())
c=[0]*(n-1);s=[0]*(n-1);f=[0]*(n-1)
for i in range(n-1):
  c[i],s[i],f[i]=map(int,input().split())
  
for i in range(n):
  ans=0
  for j in range(i,n-1):
    if ans <= s[j] :
      ans = s[j] + c[j]
    elif ans%f[j] == 0:
      ans += c[j]
    else:
      ans += c[j] + (f[j]-ans)%f[j]
  print(ans)
i=0
while True:
    i=i+1
    Indata = int(input())
    if Indata == 0:
        break
    else:
        print("Case" +str(i) + ": " + str(Indata)
    
    
    



### FIXED CODE ###

i=0
while True:
    Indata = int(input())
    if Indata == 0:
        break
    else:
        i=i+1
        print("Case " +str(i) + ": " + str(Indata))
n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))

ans = [0 for _ in range(n)]

def journey(u, p, bit):
    ans[u] = bit
    for v, w in tree[u]:
        if v == p: continue
        if w % 2 == 0: journey(v, u, bit)
        else: journey(v, u, 1-bit)
    
journey(0, -1, 0)
[print(x) for x in ans]

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    tree[u].append((v, w))
    tree[v].append((u, w))

ans = [0 for _ in range(n)]

def journey(u, p, bit):
    ans[u] = bit
    for v, w in tree[u]:
        if v == p: continue
        if w % 2 == 0: journey(v, u, bit)
        else: journey(v, u, 1-bit)
    
journey(0, -1, 0)
[print(x) for x in ans]
from functools import reduce

def inv(n):
    return p - inv(p%n) * (p//n)%p

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(lambda x, y: (x*y)%p, range(n, n - r, -1))
    inv_denom = reduce(lambda x, y: inv((x*y)%p), range(1, r + 1))
    return (numer * inv_denom) % p

p = 10 ** 9 + 7
n, a, b = map(int, input().split())

ans = pow(2, n, p) - 1
ans -= cmb(n, a, p) + cmb(n, b, p)
print(ans % p)


### FIXED CODE ###

def cmb(n, r, p):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res *= pow(i+1, p-2, p)
        res *= n-i
        res %= p
    return res

p = 10 ** 9 + 7
n, a, b = map(int, input().split())
ans = pow(2, n, p) - 1
ans -= cmb(n, a, p) + cmb(n, b, p)
print(ans % p)
import math
A,B,C,D = map(int,input().split())
n = B//C
m = (A-1)//C
p = B//D
q = (A-1)//D

x = B//(C*D// math.gcd(C,D))
y = (A-1)//(C*D// math.gcd(C,D))
L = (B-A+1)-((n-m)+(p-q)-(x-y))
print(L)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
e = gcd(c,d)
f = c * d // e

b_c = b // c
s_c = (a-1) // c
C = b_c - s_c

b_d = b // d
s_d = (a-1) // d
D = b_d - s_d

b_cd = b // f
s_cd = (a-1) // f
CD = b_cd - s_cd

ans = b - a + 1 - (C + D - CD)
print(ans)
nums = input().split()
nums = [int(i) for i in input().split()]
nums.sort
print(nums)

### FIXED CODE ###

nums = input().split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
 
if a > b:
    tmp = a
    a = b
    b = tmp
if b > c:
    tmp = b
    b = c
    c = tmp
if a > b:
    tmp = a
    a = b
    b = tmp
 
print(a, b, c)
a,b = map(int,input().split())

count_p = 0
count = 0

if b = 1:
    print(count)

while True:
    if count == 0:
        count_p += a
    
    else:
        count_p += a-1
    
    count += 1
    
    if count_p >= b:
        break

print(count)
    

### FIXED CODE ###

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

count_p = 0
count = 0

if b == 1:
    print(count)

else:
    while True:
        if count == 0:
            count_p += a
    
        else:
            count_p += a-1
    
        count += 1
    
        if count_p >= b:
            break

    print(count)
rom collections import Counter

s = input().strip()
c = Counter(s)
v = list(c.values())
if max(v) - min(v) > 1: 
  print("NO")
else:
  print("YES")

### FIXED CODE ###

from collections import Counter

s = input().strip() + "abc"
c = Counter(s)
v = list(c.values())
if max(v) - min(v) > 1: 
  print("NO")
else:
  print("YES")
n = int(input())
dat1 = list(map(int, input().split()))
dat2 = list(map(int, input().split()))
s1 = sum(dat1)
s2 = sum(dat2)
dp1 = [0]*20
dp2 = [0]*20
for i in range(n):
    dp1[i+1] = dp1[i] + dat1[i]
    dp2[i+1] = max(dp1[i+1] + dat2[i], dp2[i] + dat2[i])

print(dp2[n])


### FIXED CODE ###

n = int(input())
dat1 = list(map(int, input().split()))
dat2 = list(map(int, input().split()))
s1 = sum(dat1)
s2 = sum(dat2)
dp1 = [0]*200
dp2 = [0]*200
for i in range(n):
    dp1[i+1] = dp1[i] + dat1[i]
    dp2[i+1] = max(dp1[i+1] + dat2[i], dp2[i] + dat2[i])

print(dp2[n])
n,m map(int,input().split())
st=[]
for i in range(n):
  s_d=list(input())
  st.append(s_d)
cp=[]
for i in range(m):
  c_d=list(input())
  cp.append(c_d)
sc=[]
for i in range(n):
  scd=[]
  for j in range(m):
    scd_d=abs(st[i][0]-cp[j][0])+abs(st[i][1]-cp[j][1])
    scd.append(scd_d)
  sc.append(min(scd))
  
for i in range(n):
  print(sc[i])

### FIXED CODE ###

n,m=map(int,input().split())
st=[]
for i in range(n):
  s_d=list(map(int,input().split()))
  st.append(s_d)
cp=[]
for i in range(m):
  c_d=list(map(int,input().split()))
  cp.append(c_d)
sc=[]
for i in range(n):
  scd=[]
  for j in range(m):
    scd_d=abs(st[i][0]-cp[j][0])+abs(st[i][1]-cp[j][1])
    scd.append(scd_d)
  sc.append(scd.index(min(scd))+1)
  
for i in range(n):
  print(sc[i])
x1, y1, x2, y2 = map(int, input().split())

y3 = y2 + x2- x1
y4 = x2 - x1 + y1
x3 = y1 - y2 + x2
x4 = y1 - y2 + x1

print(x3 y3 x4 y4)

### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())

y3 = y2 + x2- x1
y4 = x2 - x1 + y1
x3 = y1 - y2 + x2
x4 = y1 - y2 + x1

print(x3, y3, x4, y4)
a,b = map(int,input().split())
l = list(input())
count = 0
for i in range(a):
  if 0<= int(l[i]) <= 9:
    count += 1
if l[a] != "-":
  print("No")
  exit()
for i in range(a+1,a+b+1):
  if 0<= int(l[i]) <= 9:
    count += 1
if count == a+b:
  print("Yes")
else:
  print("No")
  
  

### FIXED CODE ###

a,b = map(int,input().split())
l = list(input())
for i in range(a+b+1):
    if i == a:
        if l[i] != "-":
            print("No")
            exit()
    else:
        if l[i] == "-":
            print("No")
            exit()
print("Yes")
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A = sorted(A)
BC = sorted(BC, key=lambda x: -x[1])

lenA = len(A)
i = 0
for bc in BC:
  for j in range(bc[0]):
    if A[i] > bc[1]: break
    if i > lenA: break
    A[i] = bc[1]
    i += 1

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A = sorted(A)
BC = sorted(BC, key=lambda x: -x[1])

lenA = len(A)
i = 0
for bc in BC:
  for j in range(bc[0]):
    if i > lenA-1: break
    if A[i] > bc[1]: break
    A[i] = bc[1]
    i += 1

print(sum(A))
def is_substring(s,t,start_index):
	ok=True
	j=0
	for i in range(start_index, start_index + len(s) - len(t) + 1):
		if s[i] == t[j] or s[i] == '?':
			j+=1
		else:
			ok = False
			break
	return ok


def replace(s_list, index, changed_char):
	s_list[index] = changed_char
	t = "".join(s_list)
	return t

def main():
	s=str(input())
	t=str(input())
	s_list = list(s)

	ok=False
	for i in range(len(s) - len(t) + 1):
		j=0
		if s[i] == t[j] or s[i] == '?':
			if is_substring(s,t,i) == True:
				k=i
				for j in range(len(t)):
					s = replace(s_list, k, t[j])
#				s[k] = t[j]
					k+=1
				ok=True
				break

	if ok == True:
		for i in range(len(s)):
			if (s[i] == '?'):
				s = replace(s_list, i, 'a')

	print(s if ok == True else "UNRESTORABLE")

if __name__ == '__main__':
	main()

### FIXED CODE ###

S = input()
T = input()
ok = False
ans = []

for i in range(len(S)-len(T),-1,-1):
	tmpS = list(S)
	for j in range(len(T)):
		if tmpS[i+j] == "?":
			tmpS[i+j] = T[j]

	if "".join(tmpS[i:i+len(T)]) == T:
		ans = tmpS
		ok = True
		break

ans = "".join(ans)
if ok == False:
	print("UNRESTORABLE")
else:
	print(ans.replace("?","a"))
import math


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

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

dist_list = [abs(X - e) for e in x]
ans = dist_list[0]
for e in dist_list:
    ans = math.gcd(e, ans)


print(ans)


### FIXED CODE ###

def gcd(x, y):
    while y != 0:
        temp = y
        y = x % y
        x = temp
    return x


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

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

dist_list = [abs(X - e) for e in x]

ans = dist_list[0]
for e in dist_list:
    ans = gcd(ans, e)


print(ans)
a = ai()
x = lma()
k = [0]*a
s = 0
t = 0
for i in range(a):
    if i%2==0:
        k[s] = x[-1-i]
        s+=1
    else:
        k[-t-1] = x[-1-i]
        t+=1
print(k)

### FIXED CODE ###

import collections
def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
k= []
l = []
f = 0
def say(i):return print("Yes" if i == 0 else "No")
def Say(i):return print("YES" if i == 0 else "NO")
a = ai()
x = lma()
k = [0]*a
s = 0
t = 0
for i in range(a):
    if i%2==0:
        k[s] = x[-1-i]
        s+=1
    else:
        k[-t-1] = x[-1-i]
        t+=1
s = str(k[0])
for i in range(1,a):
    s+=" "+str(k[i])
print(s)
X = int(input())

J = np.zeros(X+1, dtype="bool")
# J[i] は、 i円の買い物ができるときにTrue, できないとFalse
J[0] = True
J[1:100] = True
J[100:106] = True
for i in range(106, X+1):
    if J[i - 100] or J[i - 101] or J[i - 102] or J[i - 103] or J[i - 104] or J[i - 105]:
        J[i] = True
    else:
        J[i] = False

if J[X] = True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

X = int(input())

import numpy as np

J = np.zeros(X+1, dtype="bool")
# J[i] は、 i円の買い物ができるときにTrue, できないとFalse
J[0] = True
J[1:100] = False
J[100:106] = True
for i in range(106, X+1):
    if J[i - 100] or J[i - 101] or J[i - 102] or J[i - 103] or J[i - 104] or J[i - 105]:
        J[i] = True
    else:
        J[i] = False

if J[X] == True:
    print("1")
else:
    print("0")