Harryxun/stf_run huggingface dataset:
t=list(input())
a=0
for i in range(1,len(t)):
    if t[i]=="?":
        if len(t)==i:
            t[i]="D"
            break
        if t[i-1]=="P":
            t[i]="D"
        elif t[i-1]=="D" and t[i+1]=="P":
            t[i]="D"
        else:
            t[i]="P"
    else:
        pass 
b=""
for i in range(len(t)):
    b+=t[i]
print(b)


### FIXED CODE ###

t=list(input())

if t[0]=="?":
    if len(t)<=2:
        t[0]="D"

    elif t[1]=="P":
        t[0]="D"
    
    else:
        t[0]="P"
for i in range(1,len(t)):
    if t[i]=="?":
        if i+1==len(t):
            t[i]="D"
            break
        if t[i-1]=="P":
            t[i]="D"
        else:
            if t[i+1]=="P":
                t[i]="D"
            else:
                t[i]="P"
b=""
for i in range(len(t)):
    b+=t[i]
print(b)
if n1 < 10:
    print(n1)
elif n1 <= 99:
    print(9)
elif n1 < 1000:
    print(9 + (n1 - 99))
elif n1 <= 9999:
    print(909)
elif n1 < 100000:
    print(909 + (n1 - 999))
else:
    print(90909)

### FIXED CODE ###

n1 = int(input())

if n1 < 10:
    print(n1)
elif n1 <= 99:
    print(9)
elif n1 < 1000:
    print(9 + (n1 - 99))
elif n1 <= 9999:
    print(909)
elif n1 < 100000:
    print(909 + (n1 - 9999))
else:
    print(90909)
import sys
sys.setrecursionlimit(2000)

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

def search(s,k, lis_p, lis_c, lis):
    if len(lis) >= k:
        return lis
    s = lis_p[s - 1]
    lis.append(lis_c[s - 1])
    return search(s, k, lis_p, lis_c, lis)

ans = -10**10
for i in range(n):
    l = search(i+1, k, p, c, [])
    d = max([sum(l[:j+1]) for j in range(len(l))])
    if d> ans:
        ans = d
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))
 
ans = -(10 ** 18)
 
for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)
 
print(ans)
n, q = map(int, input().split())
s = input()
t = [0]*(n + 1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - r[l-1])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

for i in range(q):
    print(ans[i])
from math import pi
a=2 * int(input())
print(a*pi)


### FIXED CODE ###

from math import pi
a=float(input())
print(a*a*pi, 2*a*pi)
#!/usr/bin/env python3
import math
# n進数の各位の和
def base_10_n(x,n):
    a = int(math.log(x,n))
    ans = 0
    for i in range(a,-1,-1):
        ans += x // n**i
        x %= n**i
    ans += x
    return ans

def main():
    N = int(input())
    ans = N
    for j in range(1,N//18 + 1):
        a = base_10_n(N-18*j,6)
        b = base_10_n(18*j,9)
        ans = min(ans, a+b)
    print(ans)
    # print([i for i in range(2,-1,-1)])

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import math
# n進数の各位の和


def base_10_n(x, n):
    if x == 0:
        return 0
    tmpx = x
    a = int(math.log(x, n))
    ans = 0
    for i in range(a, -1, -1):
        ans += tmpx // n**i
        tmpx %= n**i
    ans += tmpx
    return ans


def s(n, r):
    if n == 0:
        return 0
    return n % r + s(n // r, r)


def main():
    N = int(input())
    ans = 10**12
    for j in range(N+1):
        # c = base_10_n(N-j, 6)
        # d = base_10_n(j, 9)
        c = s(j,6)
        d = s(N-j,9)
        ans = min(ans, c+d)
    print(ans)


if __name__ == "__main__":
    main()
S_1,S_2,S_3 = input().split()
if s_1 == s_2 && s_2 == s_3:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S = input()
if S == "AAA" or S == "BBB":
  print("No")
else:
  print("Yes")
import math
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N,K = LI()

ans = K*(K-1)**(N-1)
print(ans)

### FIXED CODE ###

import math
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N,K = LI()

ans = K*(K-1)**(N-1)
print(ans)
def To_Infinity(s , k):

    ans = 0

    if s[0] == 1:
        if k == 1:
            ans = 1
        else:
            ans = s[1]
    else:
        ans = s[0]

    return ans
def main():
    s = list(int(input()))
    k = int(input())
    print(To_Infinity(s , k))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def To_Infinity(s , k):

    ans = ""

    s1 = s.lstrip("1")

    if k - (len(s) - len(s1)) > 0:
        ans = s1[0]
    else:
        ans = "1"

    return ans
def main():
    s = str(input())
    k = int(input())
    print(To_Infinity(s , k))

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-


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

numbers = []
for i in range(Q):
    numbers.append([int(j) for j in input().split()])

numbers = sorted(numbers , key = lambda x:-x[1])
#print(numbers)


kouho = ["9"*(N)]
#print(kouho)
for a, b , c ,d in numbers:
    for k in kouho:
        if int(k[b-1]) - int(k[a-1]) != c:
            #Eprint(k[a-1:] , k[:a-1])
            new_k = k[:a-1] + str(int(k[b-1])-c) +  k[a:]
            kouho.append(new_k)
            kouho = list(set(kouho))

#print(sorted(kouho))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''
kouho = []
for password in range(0,10**(N-1)):
    password = "9" + str(password).zfill(N-1)
    kouho.append(''.join(list(reversed(password))))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''


### FIXED CODE ###

import itertools

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

numbers = []
for i in range(Q):
    numbers.append([int(j) for j in input().split()])


A = list(itertools.combinations_with_replacement(range(1,M+1),N))

answer = 0
for k in  A:
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    if answer < ans:
        answer = ans
print(answer)
lst = []
for i in range(5):
    s=input()
    lst[i]=s
k = int(input())

c=0
for j in range(4):
    lgth=abs(lst[j]-lst[j+1])
    if lgth>k:
        print(':(')
    elif k=3 and lgth<=k:
        print('Yay!')

### FIXED CODE ###

import itertools

lst = [None]*5
for i in range(5):
    s=input()
    lst[i]=s
k = int(input())

lst_sub=[]
lst_C = list(itertools.combinations(lst,2))
for j in range(len(lst_C)):
    sub = abs(int(lst_C[j][0])-int(lst_C[j][1]))
    lst_sub.append(sub)

if max(lst_sub)>k:
    print(":(")
else:
    print("Yay!")
from copy import deepcopy

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

index = [i for i in range(N)]
index = sorted(index, key=lambda i: A[i], reverse=True)

print(A)
print(index)


def LorR(index, res):
    i = index[0]
    dist = max(i, N - 1 - i)
    end = False
    cand1 = cand2 = 0
    while not end:
        j = i + dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand1 = A[i] * dist + loop(index[1:], r)
            end = True

        j = i - dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand2 = A[i] * dist + loop(index[1:], r)
            end = True

        dist -= 1
    return max(cand1, cand2)


def loop(index, res):
    if not index:
        return 0

    num = 0
    a = A[index[0]]
    while num < len(index) and A[index[num]] == a:
        num += 1

    cand = [0] * num
    for i in range(num):
        ind = deepcopy(index)
        head = ind.pop(i)
        ind.insert(0, head)
        cand[i] = LorR(ind, res)

    return max(cand)


print(loop(index, [False] * N))


### FIXED CODE ###

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

A = sorted([(val, pos) for pos, val in enumerate(A)], reverse=True)

dp = [0]
for i, (val, pos) in enumerate(A):
    ldp = [e + val * abs(pos - (i - r)) for r, e in enumerate(dp)]
    rdp = [e + val * abs(N - 1 - r - pos) for r, e in enumerate(dp)]
    dp = [max(L, R) for L, R in zip(ldp + [0], [0] + rdp)]

print(max(dp))
import math

line = list(map(int, input().split(" ")))
N = line[0]
D = line[1]

bord = math.ceil(N/(2*D+1))

print(bord)


### FIXED CODE ###

r=int(input())
S=3*r*r
print(S)
import heapq
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q=[[-A[0]-B[0]-C[0],0,0,0]]
heapq.heapify(Q)
ans=[]
ijk={(0,0,0)}
while len(ans)<=K:
  abc,i,j,k=heapq.heappop(Q)
  if i+1<X and  not (i+1,j,k) in ijk:
    ijk.add((i+1,j,k))
    heapq.heappush(Q,[-A[i+1]-B[j]-C[k],i+1,j,k])
  if j+1<Y and  not (i,j+1,k) in ijk:
    ijk.add((i,j+1,k))
    heapq.heappush(Q,[-A[i]-B[j+1]-C[k],i,j+1,k])
  if k+1<Z and  not (i,j,k+1) in ijk:
    ijk.add((i,j,k+1))
    heapq.heappush(Q,[-A[i]-B[j]-C[k+1],i,j,k+1])
  ans.append(-abc)
for i in ans:
  print(i)

### FIXED CODE ###

import heapq
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q=[[-A[0]-B[0]-C[0],0,0,0]]
heapq.heapify(Q)
ans=[]
ijk={(0,0,0)}
while len(ans)<K:
  abc,i,j,k=heapq.heappop(Q)
  if i+1<X and  not (i+1,j,k) in ijk:
    ijk.add((i+1,j,k))
    heapq.heappush(Q,[-A[i+1]-B[j]-C[k],i+1,j,k])
  if j+1<Y and  not (i,j+1,k) in ijk:
    ijk.add((i,j+1,k))
    heapq.heappush(Q,[-A[i]-B[j+1]-C[k],i,j+1,k])
  if k+1<Z and  not (i,j,k+1) in ijk:
    ijk.add((i,j,k+1))
    heapq.heappush(Q,[-A[i]-B[j]-C[k+1],i,j,k+1])
  ans.append(-abc)
for i in ans:
  print(i)
N = int(input())
L = [ int(input()) for i in range(N)]
L.sort()

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a * b / gcd(a, b)

x = L[0]
for i in range(len(L)-1):
    y = lcm(x, L[i+1])
    x = y
    
print(int(x))

### FIXED CODE ###

N = int(input())
L = [ int(input()) for i in range(N)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

x = L[0]
for i in range(len(L)-1):
    y = lcm(x, L[i+1])
    x = y
    
print(x)
# -*- coding: utf-8 -*-

import bisect

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0

for i in range(n):
    Ac[i] = bisect.bisect_left(Ap, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(Cp, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp


count = 0
for i in range(n):
    count += Ac[i]*Cc[i]

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import bisect
 
n = int(input())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
 
Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0
 
for i in range(n):
    Ac[i] = bisect.bisect_left(A, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(C, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp
 
 
count = 0
for i in range(n):
    count += Ac[i]*Cc[i]
 
print(count)
def main():
    X, Y, A, B, C = [int(i) for i in input().split()]
    red = [int(i) for i in input().split()]
    blue = [int(i) for i in input().split()]
    noc = [int(i) for i in input().split()]
    red = sorted(red)[-X:]
    blue = sorted(blue)[-Y:]
    rb = sorted(red + blue)
    score = sum(rb)
    noc = sorted(noc)[::-1]
    print(rb)
    print(noc)

    s_noc = 0
    s_rb = 0
    for i in range(min(A+B, C)):
        if rb[i] > noc[i]:
            break
        s_noc += noc[i]
        s_rb += rb[i]

    print(score + s_noc - s_rb)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    X, Y, A, B, C = [int(i) for i in input().split()]
    red = [int(i) for i in input().split()]
    blue = [int(i) for i in input().split()]
    noc = [int(i) for i in input().split()]
    red = sorted(red)[-X:]
    blue = sorted(blue)[-Y:]
    rb = sorted(red + blue)
    score = sum(rb)
    noc = sorted(noc)[::-1]

    s_noc = 0
    s_rb = 0
    for i in range(min(len(rb), len(noc))):
        if rb[i] > noc[i]:
            break
        s_noc += noc[i]
        s_rb += rb[i]

    print(score + s_noc - s_rb)


if __name__ == '__main__':
    main()
from itertools import accumulate

N  = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]

# earliest deadline first
AB.sort(key=lambda x: x[1])

# 累積時刻とデッドライン
tB = accumulate(AB, lambda x, y: (x[0] + y[0], y[1]))

yes = all(t <= b for t, b in tB)
print('Yes' if yes else 'No')


### FIXED CODE ###

from itertools import accumulate

N  = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]

# earliest deadline first
AB.sort(key=lambda x: x[1])

# 累積時刻とデッドライン
tB = accumulate(AB, lambda x, y: (x[0] + y[0], y[1]))

yes = all(t <= b for t, b in tB)
print('Yes' if yes else 'No')
D,T,S=int(input().split())
if D/S<=T:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

D,T,S=map(int,input().split())
if D/S<=T:
  print('Yes')
else:
  print('No')
a,b,c=input().split();print('YNEOS'[a[-1]+c[0]!=b[::len(b)-1]::2])

### FIXED CODE ###

a,b,c=input().split();print('YNEOS'[a[::-1][0]!=b[0]or b[::-1][0]!=c[0]::2])
def partition(a,p,r):
    x=int(a[r][1:])
    i=p-1
    for j in range(p,r):
        if(int(a[j][1:])<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

b=list(a)
strr_bubble_sort(b,n)
c=list(a)
quicksort(c,0,n-1)

d=dict()
i=0
x="-1"
for i in c:
    if(x!=i[1:]):
        d[i[1:]]=[i[:1]]
        x=i[1:]
    else:
        d[x].append(i[:1])
    print(d)

message="Stable"

for i in reversed(a):
    if(i[1:] in d):
        print(d)
        if(d[i[1:]].pop()!=i[:1]):
            message="Not stable"
            break

print(message)

for i in c:
    print("%s %s"%(i[:1],i[1:]))

### FIXED CODE ###

def partition(a,p,r):
    x=int(a[r][1:])
    i=p-1
    for j in range(p,r):
        if(int(a[j][1:])<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

c=list(a)
quicksort(c,0,n-1)

d=dict()
i=0
x="-1"
for i in c:
    if(x!=i[1:]):
        d[i[1:]]=[i[:1]]
        x=i[1:]
    else:
        d[x].append(i[:1])

message="Stable"

for i in reversed(a):
    if(i[1:] in d):
        if(d[i[1:]].pop()!=i[:1]):
            message="Not stable"
            break

print(message)

for i in c:
    print("%s %s"%(i[:1],i[1:]))
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
  PY[i].append(i)

PY1 = sorted(PY)
#print(PY)

for i in range(M):
  X = str(PY1[i][0])#県の番号
  if i >= 1:#市の番号
    #print(PY)
    if PY1[i][0] == PY1[i-1][0]:
      Y = int(Y) + 1
    else:
      Y = 1
  else:
    Y = 1
  while len(str(X)) <= 5:#6桁にするための処理
    X = "0" + X
  while len(str(Y)) <= 5:
    Y = "0" + str(Y)
  PY1[i][1] = X + Y#文字列の結合
#print(PY)
PY2 = sorted(PY1, key = lambda x:x[2])

for i in range(M):
  print(PY2[i][1])
  


### FIXED CODE ###

N, M = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
  PY[i].append(i)

PY1 = sorted(PY)
#print(PY)

for i in range(M):
  X = str(PY1[i][0])#県の番号
  if i >= 1:#市の番号
    #print(PY)
    if PY1[i][0] == PY1[i-1][0]:
      Y = int(Y) + 1
    else:
      Y = 1
  else:
    Y = 1
  while len(str(X)) <= 5:#6桁にするための処理
    X = "0" + X
  while len(str(Y)) <= 5:
    Y = "0" + str(Y)
  PY1[i][1] = str(X) + str(Y) #文字列の結合
#print(PY)
PY2 = sorted(PY1, key = lambda x:x[2])

for i in range(M):
  print(PY2[i][1])
def visit(u):
    global color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        if (color[v] == WHITE):
            visit(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1
for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

### FIXED CODE ###

def dfs(u):
    global dfs_color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
               dfs(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(tmp[1]):
        M[tmp[0]-1][tmp[j+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
t = 1

for u in range(n):
    if (color[u] == WHITE):
        dfs(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for _ in range(0,M):
    b,c=map(int,input().split())
    B.append([c,b])
A.sort();B.sort(reverse=True)
cnt=0
fin=False
for b in B:
    for i in range(0,b[1]):
        if A[cnt]<b[0]:
            A[cnt]=b[0]
            cnt+=1
        else:
            fin=True
            break
    if fin:
        break
print(sum(A))



### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for _ in range(0,M):
    b,c=map(int,input().split())
    B.append([c,b])
A.sort();B.sort(reverse=True)
cnt=0
fin=False
for b in B:
    for i in range(0,b[1]):
        if cnt>N-1:
            fin=True
            break
        if A[cnt]<b[0]:
            A[cnt]=b[0]
            cnt+=1
        else:
            fin=True
            break
    if fin:
        break
print(sum(A))
if "9" == N[0] or "9" == N[1]:
        print( "YES" )
else:
    print( "NO" )

### FIXED CODE ###

N = input()

if "9" in N:
    print( "Yes" )
else:
    print( "No" )
s = input()
l = len(s)
ans = 0
for i in range(2**(l-1)):
    eval = ''
    for j in range(l):
        if ((i >> j) & 1):
            eval += s[j] + '+'
        else:
            eval += s[j]
    ans += eval(eval)

### FIXED CODE ###

s = input()
l = len(s)
ans = 0
for i in range(2**(l-1)):
    e = ""
    for j in range(l):
        if ((i >> j) & 1):
            e += s[j] + "+"
        else:
            e += s[j]
    ans += eval(e)
print(ans)
N, A, B, C = list(map(int, input().split()))
s = [input() for _ in range(N)]

DP = [[0] * 3 for _ in range(N + 1)]
DP[0] = [A, B, C]

L = [""] * N
R = {}
R[0] = "A"
R[1] = "B"
R[2] = "C"
A = []
B = []
  for i in range(N):
    t = s[i]
    if t == "AB":
      x = 0
      y = 1
    if t == "BC":
      x = 1
      y = 2
    if t == "AC":
      x = 0
      y = 2
    if DP[i][y] != 0:
      DP[i + 1] = DP[i]
      DP[i + 1][x] += 1
      DP[i + 1][y] -= 1
      L[i] = R[x]
      if x == 0:
        A.append([i, y])
      else:
        B.append([i, y])
    elif DP[i][x] != 0:
      DP[i + 1] = DP[i]
      DP[i + 1][x] -= 1
      DP[i + 1][y] += 1
      L[i] = R[y]
    else:
      if x == 0:
        if len(B) == 0:
          print("No")
          exit()
        z = 1
        k, n = pop(B)
      if x == 1:
        if len(A) == 0:
          print("No")
          exit()
        z = 0
        k, n = pop(A)
      DP[i + 1] = DP[i]
      DP[i + 1][z] -= 2
      DP[i + 1][n] += 2
      if n == x:
        x, y = y, x
      DP[i + 1][x] += 1
      DP[i + 1][y] -= 1
      if DP[i + 1][z] < 0:
        print("No")
        exit()
      L[i] = R[x]
      L[t] = R[y]

  print("Yes")
  for i in L:
    print(i)


### FIXED CODE ###

N, A, B, C = list(map(int, input().split()))
s = [input() for _ in range(N)]

DP = [[0] * 3 for _ in range(N + 1)]
DP[0] = [A, B, C]

L = [""] * N
R = {}
R[0] = "A"
R[1] = "B"
R[2] = "C"
A = []
B = []
for i in range(N):
  t = s[i]
  if t == "AB":
    x = 0
    y = 1
  if t == "BC":
    x = 1
    y = 2
  if t == "AC":
    x = 0
    y = 2
  if DP[i][y] != 0:
    DP[i + 1] = DP[i]
    DP[i + 1][x] += 1
    DP[i + 1][y] -= 1
    L[i] = R[x]
    if x == 0:
      A.append([i, y])
    else:
      B.append([i, y])
  elif DP[i][x] != 0:
    DP[i + 1] = DP[i]
    DP[i + 1][x] -= 1
    DP[i + 1][y] += 1
    L[i] = R[y]
  else:
    if x == 0:
      if len(B) == 0:
        print("No")
        exit()
      z = 1
      k, n = B.pop()
    if x == 1:
      if len(A) == 0:
        print("No")
        exit()
      z = 0
      k, n = A.pop()
    DP[i + 1] = DP[i]
    DP[i + 1][z] -= 2
    DP[i + 1][n] += 2
    if n == x:
      x, y = y, x
    DP[i + 1][x] += 1
    DP[i + 1][y] -= 1
    if DP[i + 1][z] < 0:
      print("No")
      exit()
    L[i] = R[x]
    L[k] = R[y]

print("Yes")
for i in L:
  print(i)
import heapq

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
q=[]
for i in range(n):
  heapq.heappush(q,(-arr2[i],i))
cnt=0
num=0
while 1:
  val,pos=-heapq.heappop(q)
  diff=arr2[pos-1]+arr2[(pos+1)%n]
  move=(val-diff)//diff+1
  if move<=0:
    break
  tmp=arr2[pos]-diff*move
  if tmp<=0:
    break
  arr2[pos]=tmp
  heapq.heappush(q,-tmp)
  if tmp==arr1[pos]:
    num+=1
  cnt+=move
  if num==n:
    break
for i in range(n):
  if arr1[i]!=arr2[i]:
    print(-1)
    break
else:
  print(cnt)

### FIXED CODE ###

import heapq

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
q=[]
for i in range(n):
  if arr2[i]!=arr1[i]:
    heapq.heappush(q,(-arr2[i],i))
cnt=0
while q:
  val,pos=heapq.heappop(q)
  val*=-1
  diff=arr2[pos-1]+arr2[(pos+1)%n]
  move,tmp=divmod(val-arr1[pos],diff)
  if move==0:
    break
  cnt+=move
  tmp+=arr1[pos]
  arr2[pos]=tmp
  if tmp!=arr1[pos]:
    heapq.heappush(q,(-tmp,pos))
for i in range(n):
  if arr1[i]!=arr2[i]:
    print(-1)
    break
else:
  print(cnt)