Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1
def dfs(par,cur,num):
    global ans
    ans*=num
    ans%=mod
    if par==-1: #ルートノードの時は
        num=K-1  #K-1色使用できる
    else:       #ルートノードじゃない時は
        num=K-2  #K-2色使用できる
    for to in al[cur]:
        if to!=par: #遷移候補が親でなければ、遷移
            dfs(cur,to,num)
            num-=1
dfs(-1,1,K)

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,K=map(int, sys.stdin.readline().split())

 #階乗　前計算
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, K+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def npr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[n-r]) %mod



nl=[ [] for i in range(N+1) ]	#隣接リスト
C=[ 0 for i in range(N+1) ]	#入次数: 頂点に入ってくる辺数
 
for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	C[a]+=1
	nl[b].append(a)
	C[b]+=1


start=1
Visit=[ None for i in range(N+1) ] 
Visit[start]=1
 
p=None		#Parent
q=deque()
q.append( (p,start) )

ans=K

while q:
	p,current=q.popleft()
	flag=0
	for to in nl[current]:
		if Visit[to] is None:
			Visit[to]=1
			q.append( (current,to) )
			flag=1
	if p is None and flag:
		ans*=npr(K-1,C[current])
	elif p is not None and flag:
		ans*=npr(K-2,C[current]-1)
	ans%=mod
		

print ans
n=int(input())
a= [list(input()) for _ in range(n)]
nex=[]
k=1
for i in range(len(a)):
    #if k-1==-1:k-1=0
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass

### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
nex=[]
k=1
for i in range(len(a)):
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass
cnt_A=0
cnt_B=0
cnt_C=0
cnt_D=0
max_noudo=0
water=0
sugar=0
while cnt_A*100*A <= F:
  cnt_B=0
  while cnt_B*100*B <= F-cnt_A*100*A:
    cnt_C=0
    while cnt_C*C <= F-cnt_A*100*A-cnt_B*100*B:
      cnt_D=0
      while cnt_D*D <= F-cnt_A*100*A-cnt_B*100*B-cnt_C*C:
        if (cnt_A*A+cnt_B*B)*E >= cnt_C*C+cnt_D*D >0:
          if max_noudo < 100*(cnt_C*C+cnt_D*D)/(cnt_A*A+cnt_B*B):
            max_noudo = 100*(cnt_C*C+cnt_D*D)/(cnt_A*A+cnt_B*B)
            water=cnt_A*A*100+cnt_B*B*100+cnt_C*C+cnt_D*D
            sugar=cnt_C*C+cnt_D*D
          cnt_D+=1
        else:
          break
      cnt_C+=1
    cnt_B+=1
  cnt_A+=1

print(str(water)+' '+str(sugar))

### FIXED CODE ###

A,B,C,D,E,F=map(int, input().split())
cnt_A=0
cnt_B=0
cnt_C=0
cnt_D=0
max_noudo=0
water=A*100
sugar=0
while cnt_A*100*A <= F:
  cnt_B=0
  while cnt_B*100*B <= F-cnt_A*100*A:
    cnt_C=0
    while cnt_C*C <= F-cnt_A*100*A-cnt_B*100*B:
      cnt_D=0
      while cnt_D*D <= F-cnt_A*100*A-cnt_B*100*B-cnt_C*C:
        if (cnt_A*A+cnt_B*B)*E >= cnt_C*C+cnt_D*D >0:
          if max_noudo < 100*(cnt_C*C+cnt_D*D)/(cnt_A*A+cnt_B*B):
            max_noudo = 100*(cnt_C*C+cnt_D*D)/(cnt_A*A+cnt_B*B)
            water=cnt_A*A*100+cnt_B*B*100+cnt_C*C+cnt_D*D
            sugar=cnt_C*C+cnt_D*D
        cnt_D+=1
      cnt_C+=1
    cnt_B+=1
  cnt_A+=1
 
print(water,sugar)
def search(n,d,t):
    b = 0
    e = n
    r = 0
    while True:
        r += 1
        if b > e:
            return r
        else:
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)
    

### FIXED CODE ###

def search(n,d,t):
    b = 0
    e = n-1
    r = 0
    while True:
        if b > e:
            return r
        else:
            r += 1
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)
a = [-1]

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

for _ in range(M):
    a.append(int(input()))
a.append(N+1)

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

#print(b)

def func(n):
    if n == -1:
        retval = 0
    elif n >= 0 and n <= 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)


### FIXED CODE ###

a = [-1]

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

for _ in range(M):
    a.append(int(input()))
a.append(N+1)

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

if min(b) < 0:
    print(0)
else:
    result = 1

    f_list = []
    for i in range(max(b)+1):
        if i == 0 or i == 1:
            f_list.append(1)
        else:
            f_list.append(f_list[i-2] + f_list[i-1])

    for i in range(M+1):
        result = result * f_list[b[i]]
        result = result % (10**9 + 7)

    print(result)
import sys
import bisect
input = sys.stdin.readline

def main():
    N = int(input())
    S = [int(s) for s in input().split()]
    S.sort()

    cur = []
    cur.append(S.pop(-1))

    for i in range(N):
        nxt = [j for j in cur]
        bl = len(S)
        for x in cur:
            bl = bisect.bisect_left(S,x,lo=0,hi=bl)
            if bl==0:
                return("No")
            else:
                nxt.append(S.pop(bl-1))
        nxt.sort(reverse=True)
        cur = [j for j in nxt]
    return("Yes")

if __name__ == "__main__":
    print(main())

### FIXED CODE ###

import sys

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])


def main():
    N = I()
    S = sorted(LI(),reverse=True)

    flag = [True]*len(S)

    cur = []
    cur.append(S[0])
    flag[0] = False

    for i in range(N):
        nxt = [x for x in cur]
        j = 0

        for k in range(len(S)):
            if j >= len(cur):
                break
            elif flag[k] and S[k]<cur[j]:
                nxt.append(S[k])
                j+=1
                flag[k] = False
        if len(cur) != j:
            return("No")
        cur = sorted(nxt,reverse=True)
    return("Yes")

if __name__ == "__main__":
    print(main())
2 3
1 32
2 63
1 12

### FIXED CODE ###

n,m = map(int,input().split())
mat = []
for i in range(n):
    mat.append(list(map(int,input().split())))
#ここまで情報のインプット

#基本方針はまだ扱っていない最小のお金を持つ栄養ドリンクをとっていく。
#つまりは値がちいさいものから順に在庫が切れるまで選択するということ。

ans = 0
i = 0
mat.sort()
#値でsortする
while True:
    if m - mat[i][1] > 0:
        ans += mat[i][1]*mat[i][0]
        m -= mat[i][1]
        i += 1
    else:
        ans += mat[i][0] *m
        break
print(ans)
def solve():
    A, B, K = map(int, input().split())
    ans = list(range(A, B + 1))
    if B - A >= K * 2:
        ans = sorted((set(ans[:K] + ans[-K:])), key=ans.index)

    for a in ans:
        print(a)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

def solve():
    A, B, K = map(int, input().split())
    for i in range(A, min(A+K, B+1)):
        print(i)
    for j in range(max(A+K, B-K+1), B+1):
        print(j)


if __name__ == "__main__":
    solve()
n, m = map(int, input().split())
d = {i+1 : [] for i in range(n)}
for _ in range(n):
  a, b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
ans = 0
def go(c, rem):
  global ans
  if not len(rem):
    ans += 1
    return
  for cand in d[c]:
    if cand in rem:
      i = rem.index(cand)
      go(cand, rem[:i] + rem[i+1:])
go(1, list(range(2, n+1)))
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
d = {i+1 : [] for i in range(n)}
for _ in range(m):
  a, b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
ans = 0
def go(c, rem):
  global ans
  if not len(rem):
    ans += 1
    return
  for cand in d[c]:
    if cand in rem:
      i = rem.index(cand)
      go(cand, rem[:i] + rem[i+1:])
go(1, list(range(2, n+1)))
print(ans)
a,b=map(int,input().spllit())
print(max(a+b,a-b,a*b))

### FIXED CODE ###


a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
O=input()
E=input()
s=''
for i in range (len(O)):
    s+=O[i]+E[i]
print(s)


### FIXED CODE ###

O=input()
E=input()
s=''
if len(O)==len(E):
    for i in range (len(O)):
        s+=O[i]+E[i]
else:
    for i in range (len(O)-1):
        s+=O[i]+E[i]
    s+=O[-1]
print(s)
N = input()
a = 0
for i in range(1, N + 1):
    if i % 5 != 0 and i % 3 != 0:
        a += i
print(a)

### FIXED CODE ###

n = int(input())
a = 0
for i in range(1, n + 1):
    if i % 5 != 0 and i % 3 != 0:
        a += i
print(a)
n=int(input())
l=[]
for i in range(n):
  s=int(input())
  l.append(s)


a=round(sum(l)/n)
k=0
for j in range(n):
  k+=(l[j]-a)**2

print(k)
  

### FIXED CODE ###

n=int(input())
l= list(int(i) for i in input().split())
a=int(round(sum(l)/n))
k=0
for j in l:
  k = k + (j-a)**2
print(k)
n,k = map(int, input().split())
p = [int(e) for e in input().split()]

e = [(q+1.0)/2 for q in p]

max = 0
for i in range(n-k+1):
  s = e[i]+e[i+1]+e[i+2]
  if max < s:
    max = s
    
print(max)


### FIXED CODE ###

n,k = map(int, input().split())
p = [int(e) for e in input().split()]
s = sum(p[0:k])
max = s
for i in range(n-k):
  s = s - p[i] + p[i+k]
  if max < s:
    max = s
    
ex = (max+k)/2.0
print(ex)
S = input()

subStringList = []
length = len(S)

for i in range(length) :
    for j in range(1,length+1):
        if (i+j <= length) :
            subStringList.append(S[i:i+j])
        else:
            break


for s in subStringList[:]:
    for letter in s:
        if (not(letter in "ATGC")):
            subStringList.remove(s)
            break

print(len(max(subStringList, key=len)))


### FIXED CODE ###

S = input()

subStringList = [S]
length = len(S)

counter = 0
before = 1

while (not(counter == before)):
    before = counter
    for s in subStringList[:]:
        for letter in s:
            if (not(letter in "ATGC")):
                subStringList += s.split(letter)
                subStringList.remove(s)
                counter = len(subStringList)
                break

print(len(max(subStringList,key=len)))
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from decimal import Decimal

a,b,x = II()

h = Decimal((x-a**2*b/2)*2/(a**2))
if h>=0:
    r = math.degrees(math.atan(a/(b-h)))
    print(90-r)
else:
    z = Decimal(2*x/(a*b))
    r = math.degrees(math.atan(z/b))
    print(90-r)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

a,b,x = II()

h = (x-a**2*b/2)*2/(a**2)
if h>=0:
    if b-h==0:
        print(0)
    else:
        r = math.degrees(math.atan(a/(b-h)))
        print(90-r)
else:
    z = 2*x/(a*b)
    r = math.degrees(math.atan(z/b))
    print(90-r)
import sys
print(sys.split().index("0") + 1)

### FIXED CODE ###

print(input().split().index("0") + 1)
N = int(input())
S = input()

for i in range(N - 1, -1, -1):
    if S[i] == ".":
        right_white = i
        break

print(min(S.count("."), S[:right_white].count("#")))


### FIXED CODE ###

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

white = [0] * (N + 1)
for i in range(N):
    if S[i] == ".":
        white[i + 1] = white[i] + 1
    else:
        white[i + 1] = white[i]

ans = N
for i in range(N + 1):
    tmp = (i - white[i]) + (white[-1] - white[i])
    if tmp < ans:
        ans = tmp

print(ans)
a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a,b)+min(c+d))

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a,b)+min(c,d))
from functools import lru_cache

M, N = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
VW = sorted(VW, key=lambda x:(x[0]/x[1],x[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h<=0:
        return 0
    else:
        best = float("inf")
        for a,b in VW:
            val = b+dp(h-a)
            if val < best:
                best = val
            else:
                break
        return best
print(dp(M))


### FIXED CODE ###

import numpy as np
h, N = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
VW = np.array(sorted(VW, key=lambda x:(x[0]/x[1],x[0])))
a = VW[:, 0]
b = VW[:, 1]

dp = np.zeros(10**4+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()
print(dp[h])
A,B,C,X=map(int,input().split()) #500,100,50, total
#X=500*a+100*b+50*c
flag=0
count=0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if X==500*a+100*b+50*c:
        count=count+1
        flag=1
if flag==1:
  print(count)
else:
  print(0)
        



### FIXED CODE ###

#A,B,C,X=map(int,input().split()) #500,100,50, total
#X=500*a+100*b+50*c
A=int(input())
B=int(input())
C=int(input())
X=int(input())
count=0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if X==500*a+100*b+50*c:
        count=count+1
print(count)
C = [list(map(int,input().split())) for l in range(3)]

C = np.array(C)

cross1 = C[0][0] + C[1][1] + C[2][2]
cross2 = C[0][2] + C[1][1] + C[2][0]
if(cross1 == cross2 and np.sum(C)/6 == cross1/2):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
import numpy as np
from fractions import gcd
import collections

C = [list(map(int,input().split())) for l in range(3)]

C = np.array(C)

cross1 = C[0][0] + C[1][1] + C[2][2]
cross2 = C[0][2] + C[1][1] + C[2][0]
if(cross1 == cross2 and np.sum(C)/6 == cross1/2):
    print('Yes')
else:
    print('No')
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(S)
    print(answer)


def resolve(q, S, D, H, W):
    cell_list = list()
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

def plist(n):
	sqrt = int(math.sqrt(n))
	p = [1]*(sqrt+3)
	p[0] = 0
	for i in range(2,int(math.sqrt(sqrt))+2):
		if p[i]:
			p[2*i::i] = [0 for x in range(2*i,sqrt+1,i)]
	return p

def get_pfact(p,n):
	div = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+3):
		if p[i] and n%i == 0:
			div.append(i)
	return div

def phai(n,div):
	ans = n
	for pf in div:
		ans *= (1-1/float(pf))
	return int(ans)

# main	
n = int(raw_input())
p = plist(n)
div = get_pfact(p,n)
print phai(n,div)

### FIXED CODE ###

def phi(n):
	r = n
	i = 2
	while i*i <= n:
		if n%i==0:
			r -= r/i
			while n%i==0:
				n /= i
		i += 1
	if n>1: r-= r/n
	return r

n = int(raw_input())
print phi(n)
import math
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

A,B,C,D = na()
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
ee = lcm(C,D)
A = A-1
cc = B//C
dd = B//D
ansb = cc+dd-B//ee

ansa = A//C+A//D-A//ee

print(B-A-(ansb-ansa))


### FIXED CODE ###

import fractions
na = lambda: list(map(int, input().split()))
A,B,C,D = na()
ee = (C * D)//fractions.gcd(C, D)
A = A-1
cc = B//C
dd = B//D
ansb = cc+dd-B//ee
ansa = A//C+A//D-A//ee
print(B-A-(ansb-ansa))
s = input() + "T"
x, y = map(int, input().split())
N = len(s)



for i in range(N):
    if s[i] == "F":
        x -= 1
    else:
        cnt_Y = True
        index = i + 1
        break

steps_X = []
steps_Y = []

while index < N:
    cnt = 0
    for j in range(index, N):
        if s[j] == "F":
            cnt += 1
        else:
            if cnt_Y and cnt != 0:
                steps_Y.append(cnt)
            elif not cnt_Y and cnt != 0:
                steps_X.append(cnt)
            cnt_Y = not cnt_Y
            index = j
            break
    index += 1

    
K = 8000*2+1
dp = [[False] * (8000*2+1) for _ in range(2)]
dp[0][0] = True


for i, t in enumerate(steps_X):
    trues_p = [idx + t for idx, v in enumerate(dp[i%2]) if v == True]
    trues_n = [idx - t for idx, v in enumerate(dp[i%2]) if v == True]
    for tr in trues_p:
        dp[(i+1)%2][tr] = True
    for tr in trues_n:
        dp[(i+1)%2][tr] = True

if dp[len(steps_X) %2][x] == False:
    print("No")
    import sys
    sys.exit()

dp = [[False] * (8000*2+1) for _ in range(2)]
dp[0][0] = True

for i, t in enumerate(steps_Y):
    trues_p = [idx + t for idx, v in enumerate(dp[i%2]) if v == True]
    trues_n = [idx - t for idx, v in enumerate(dp[i%2]) if v == True]
    for tr in trues_p:
        dp[(i+1)%2][tr] = True
    for tr in trues_n:
        dp[(i+1)%2][tr] = True

if dp[len(steps_Y) %2][y] == False:
    print("No")
    import sys
    sys.exit()

print("Yes")


### FIXED CODE ###

s = input() + "T"
x, y = map(int, input().split())
N = len(s)



for i in range(N):
    if s[i] == "F":
        x -= 1
    else:
        cnt_Y = True
        index = i + 1
        break

steps_X = []
steps_Y = []

while index < N:
    cnt = 0
    for j in range(index, N):
        if s[j] == "F":
            cnt += 1
        else:
            if cnt_Y and cnt != 0:
                steps_Y.append(cnt)
            elif not cnt_Y and cnt != 0:
                steps_X.append(cnt)
            cnt_Y = not cnt_Y
            index = j
            break
    index += 1
    
K = 10000
dp = [set() for _ in range(K)]
dp[0].add(0)

for i, t in enumerate(steps_X):
    for tmp in dp[i]:
        dp[i+1].add(tmp+t)
        dp[i+1].add(tmp-t)

# print(dp[len(steps_X)])
if x not in dp[len(steps_X)]:
    print("No")
    import sys
    sys.exit()

dp = [set() for _ in range(K)]
dp[0].add(0)
for i, t in enumerate(steps_Y):
    for tmp in dp[i]:
        dp[i+1].add(tmp+t)
        dp[i+1].add(tmp-t)

if y not in dp[len(steps_Y)]:
    print("No")
    import sys
    sys.exit()


print("Yes")
A, B, C, D = map(int, input().split())
while A > 0 and C > 0:
    C = C - B
    A = A - D
if A == 0:
    ans = 'No'
else:
    ans = 'Yes'
print(ans)


### FIXED CODE ###

S, W = map(int, input().split())
if S <= W:
    print('unsafe')
else:
    print('safe')
A, B, T = map(int, input().split())

def biscuit_gen(A,B,T):
    total = 0
    num = int(T//A)
    return B*num

print(biscuit_gen(A,B,t))

### FIXED CODE ###

A, B, T = map(int, input().split())

def biscuit_gen(A,B,T):
    total = 0
    num = int(T//A)
    return B*num

n = biscuit_gen(A,B,T)
print(n)
N = int(input())
A = [0]*N
B = [[0]*19 for x in range(19)]
C = [0]*N
D = [0]*N
a,b,c,d,e,ans = 0,['0']*9,0,0,0,0
for i in range(N):
    c = (input()+'.0').split('.')
    b = ['0']*9
    for k,v in enumerate(c[1]):
        b[k] = v
    A[i] = int(c[0]+''.join(b))

# print(*A)

for i in range(N):
    d,e = 0,0
    while (A[i] % 2 == 0) and (d <= 18):
        A[i] //= 2
        d += 1
    while (A[i] % 5 == 0) and (e <= 18):
        A[i] //= 5
        e += 1
    C[i] = d
    D[i] = e
    B[d][e] += 1

for i in range(N):
    c = C[i]
    d = D[i]
    B[c][d] -= 1
    for j in range(18-c,19):
        for k in range(18-d,19):
            ans += B[j][k]

print(ans)

### FIXED CODE ###

N = int(input())
A = [0]*N
B = [[0]*19 for x in range(19)]
C = [0]*N
D = [0]*N
a,b,c,d,e,ans = 0,['0']*9,0,0,0,0
for i in range(N):
    c = (input()+'.0').split('.')
    b = ['0']*9
    for k,v in enumerate(c[1]):
        b[k] = v
    A[i] = int(c[0]+''.join(b))

# print(*A)

for i in range(N):
    d,e = 0,0
    while (A[i] % 2 == 0) and (d < 18):
        A[i] //= 2
        d += 1
    while (A[i] % 5 == 0) and (e < 18):
        A[i] //= 5
        e += 1
    C[i] = d
    D[i] = e
    B[d][e] += 1

for i in range(N):
    c = C[i]
    d = D[i]
    B[c][d] -= 1
    for j in range(18-c,19):
        for k in range(18-d,19):
            ans += B[j][k]

print(ans)
import numpy as np
n, m = (int(i) for i in input().split())
a = np.sort(np.array([int(i) for i in input().split()]))
b, c = np.zeros(m), np.zeros(m)
for i in range(m):
    b[i], c[i] = (int(i) for i in input().split())

b = b[np.argsort(-c)]
c = c[np.argsort(-c)]
i = 0
for bb, cc in zip(b, c):
    for cnt in range(int(bb)):
        if a[i] < cc:
            a[i] = cc
        else:
            break
        i = i + 1
    else:
        continue
    break
print(sum(a))

### FIXED CODE ###

import numpy as np
n, m = (int(i) for i in input().split())
a = np.sort(np.array([int(i) for i in input().split()], dtype='int64'))
b, c = np.zeros(m, dtype='int64'), np.zeros(m, dtype='int64')
for i in range(m):
    b[i], c[i] = (int(i) for i in input().split())

b = b[np.argsort(-c)]
c = c[np.argsort(-c)]
i = 0
for bb, cc in zip(b, c):
    for cnt in range(bb):
        if a[i] < cc:
            a[i] = cc
        else:
            break
        i = i + 1
        if i >= len(a):
            break
    else:
        continue
    break
print(int(sum(a)))