Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
A = list(map(int,input().split()))



def check(A,M):
    flag = 0
    sumOfA = 0
    for i in A:
        sumOfA+=A
    condition = sumOfA/(4*M)
    if(M==1 and max(A)>condition):
        return "Yes"
    for i in A:
        if(i <= condition):
            continue
        else:
            flag+=1
            if(flag==M):
                return "Yes"
    return "No"

print(check(A,M) else "No")





### FIXED CODE ###

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



def check(A,M):
    flag = 0
    condition = sum(A)/(4*M)
    if(M==1 and max(A)>condition):
        return "Yes"
    for i in A:
        if(i < condition):
            continue
        elif(i >= condition):
            flag+=1
            if(flag==M):
                return "Yes"
    return "No"

print(check(A,M))
N = int(input())
ans = []
n = 4/N
for i in range(1,3501):
    flag = True
    for j in range(1,3501):
        if(n-1/i-1/j==0):
            continue
        k = 1/(n-1/i-1/j)
        if(int(k)==k and k>0):
            ans=[i,j,int(k)]
            flag = False
            break
    if(not flag):
        break
print(ans[0],ans[1],ans[2])

### FIXED CODE ###

N = int(input())
ans = []
n = 4/N
for i in range(1,3501):
    flag = True
    for j in range(1,3501):
        if(4*i*j-N*j-N*i==0):
            continue
        k = N*i*j/(4*i*j-N*j-N*i)
        if(int(k)==k and k>0):
            ans=[i,j,int(k)]
            flag = False
            break
    if(not flag):
        break
print(ans[0],ans[1],ans[2])
N = int(input())
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x.copy())
    B.append(x.copy())

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)



### FIXED CODE ###

N = int(input())
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x[:])
    B.append(x[:])

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)
a, b = map(int, input().split())
 
def FizzBuzz(a, b):
  total = a*b
  if a*b%2 = 0:
    print('Even')
  else:
    print('Odd')
 
FizzBuzz(a, b)

### FIXED CODE ###

a, b = map(int, input().split())
 
def FizzBuzz(a, b):
  total = a*b
  if total % 2 == 0:
    print('Even')
  else:
    print('Odd')
 
FizzBuzz(a, b)
# -*- coding: utf-8 -*-

a = int(input())
b = int(input())

if a * b % 2:
    print('Odd')
else:
    print('Even')


### FIXED CODE ###

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

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

if (a * b) % 2:
    print('Odd')
else:
    print('Even')
a=int(input().split())
print(a[0]*a[1],(a[0]+a[1])*2)

### FIXED CODE ###

x,y=[int(i) for i in input().split()]
print(x*y,(x+y)*2)
n = int(input())
s = int(input())

flag = False

if s == n:
  print(n+1)
  exit()

def chk(b, n):
  if n//b == 0:
    return n
  else:
    return chk(b,n//b) + n%b

for b in range(2, int(n**0.5)+1):
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

for i in range(int(n**0.5), 0, -1):
  b = (n-s)//i + 1
  if chk(b, n) == s:
    print(b)
    flag = True
    exit()

if flag == False:
  print(-1)

### FIXED CODE ###

N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if N > K:
  print(X*K+Y*(N-K))
elif N <= K:
  print(X*N)
import math


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


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

AtoB = (B - (A - 1))

divisible_C = (B // C) - ((A - 1) // C)
divisible_D = (B // D) - ((A - 1) // D)


minLcm = lcm(C, D)

answer = 10

# divisible_CD = (B // minLcm) - ((A - 1) // minLcm)
# 
# divisible_CtoD = (divisible_C + divisible_D) - divisible_CD
# 
# answer = AtoB - divisible_CtoD

print(answer)

### FIXED CODE ###

import fractions


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


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

AtoB = (B - (A - 1))

divisible_C = (B // C) - ((A - 1) // C)
divisible_D = (B // D) - ((A - 1) // D)

minLcm = lcm(C, D)

divisible_CD = (B // minLcm) - ((A - 1) // minLcm)

divisible_CtoD = (divisible_C + divisible_D) - divisible_CD

answer = AtoB - divisible_CtoD

print(answer)
X, Y, Z = map(int, input().split())
ans = 1
length = Y+2Z
while True:
    if length > X:
        print(ans)
        break
    ans += 1
    length += Y+Z


### FIXED CODE ###

X, Y, Z = map(int, input().split())
ans = 1
length = Y+2*Z
while True:
    if length+Y+Z > X:
        print(ans)
        break
    ans += 1
    length += Y+Z
K,S = map(int,input().split())
count = 0
for i in range(0,K+1):
    X = i
    for j in range(0,K+1):
        Y = j
        for k in range(0,K+1):
            Z = k
            if ( ty == S):
                count += 1
print(count)

### FIXED CODE ###

K,S = map(int,input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if (0 <= z < K + 1):
            count += 1
print(count)
from collections import deque

def chk(i,time,a,b):
    if len(a)==0 and len(b)==0:
        return i
    if time>k:
        return i-1
    
    if len(a)==0:
        tmp_a = 10**9
    else:
        tmp_a = a.popleft()
        
    if len(b)==0:
        tmp_b = 10**9
    else:
        tmp_b = b.popleft()
        
    if tmp_a>tmp_b:
        time += tmp_b
        a.appendleft(tmp_a)
        i += 1
    else:
        time += tmp_a
        b.appendleft(tmp_b)
        i += 1
        
    tmp = chk(i,time,a,b)
    return tmp

n,m,k = map(int,input().split())
tmp_a = list(map(int,input().split()))
tmp_b = list(map(int,input().split()))
a = deque()
b = deque()
a.extend(tmp_a)
b.extend(tmp_b)
#print(a,b)

print(chk(0,0,a,b))

### FIXED CODE ###

n,m,k = map(int,input().split())
tmp_a = list(map(int,input().split()))
tmp_b = list(map(int,input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i]+tmp_a[i])
for i in range(m):
    b.append(b[i]+tmp_b[i])
#print(a)
#print(b)
ans = 0
j = m
for i in range(n+1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)
N=int(raw_input())
A=map(int,raw_input().split())
def f(x):
  cnt = 0
  while x >= 2:
    x /= 2
    cnt += 1
  return cnt
C=map(f,A)
pritn min(C)
    

### FIXED CODE ###

N=int(raw_input())
A=map(int,raw_input().split())
def f(x):
  cnt = 0
  while x >= 2 and x % 2 == 0:
    x /= 2
    cnt += 1
  return cnt
C=map(f,A)
print min(C)
input()
data = input().split().reverse()
data.reverse()
print(' '.join(data))

### FIXED CODE ###

input()
data = input().split()
data.reverse()
print(' '.join(data))
s = input()
k = int(input())
for i in range(min(len(s), k)):
  if s[i] != '1':
    print(c)
    break
else:
  print(s[k - 1])


### FIXED CODE ###

s = input()
k = int(input())
for i in range(min(len(s), k)):
  if s[i] != '1':
    print(s[i])
    break
else:
  print(s[k - 1])
import math

n,x=map(int,input().split())
z=[]

y=[]
z=list(map(int, input().split()))
z.append(x)
z.sort()

for i in range(n):
  y.append(z[i+1]-z[i])

if n==1:
  print(y[0])
else:
  gcm=math.gcd(y[0],y[1])
  for i in range(2,n):
    gcm=math.gcd(gcm,y[i])
  print(gcm)


### FIXED CODE ###

import fractions

n,x=map(int,input().split())
z=[]
y=[]
z=list(map(int, input().split()))

for i in range(n):
  y.append(abs(x-z[i]))

if n==1:
  print(y[0])
else:
  gcm=y[0]
  for i in range(n):
    gcm=fractions.gcd(gcm,y[i])
  print(gcm)
n=input()
a=input()
b=input()
print(int(b*(n-2)-(a*n-2)+1))

### FIXED CODE ###

n,a,b=map(int,input().split())
if n>1 and b>=a or n==1 and a==b: 
    print ((n-2)*(b-a)+1);
else:
    print ("0");
from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

MOD = 10**9 + 7

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできる

    # K が奇数のとき、非負要素から1つ取って偶数の場合に帰着
    # K が偶数のとき、面倒なので 2 つセットで考えて K//2 個取る問題に帰着

    if K%2 == 1:
        ans = A.pop(0)  # あらかじめ最大値を確保
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

    # 絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    cand = []  # 非負要素、負要素をそれぞれ絶対値の大きい順に 2 つずつ掛けたもの

    BIGINT = 10**9 + 1  # tmp 用
    tmp1 = BIGINT
    tmp2 = BIGINT
    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = A
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    # あとは大きい方から n 個取る
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)


### FIXED CODE ###

from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

MOD = 10**9 + 7

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできる

    # K が奇数のとき、非負要素から1つ取って偶数の場合に帰着
    # K が偶数のとき、面倒なので 2 つセットで考えて K//2 個取る問題に帰着

    if K%2 == 1:
        ans = A.pop(0)  # あらかじめ最大値を確保
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

    # 絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    cand = []  # 非負要素、負要素をそれぞれ絶対値の大きい順に 2 つずつ掛けたもの

    BIGINT = 10**9 + 1  # tmp 用
    tmp1 = BIGINT
    tmp2 = BIGINT

    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = a
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    # あとは大きい方から n 個取る
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)
AList = list(map(int,input().split()))
AList.sort()
print(abs(AList[0]-AList[1])+abs(AList[2]-AList[1])

### FIXED CODE ###

AList = list(map(int,input().split()))
AList.sort()
print(abs(AList[0]-AList[1])+abs(AList[2]-AList[1]))
N, Y = map(int, input().split())
sum = 0
is_exist = False
for i in range(N+1):
  for j in range(N+1):
    k = N - i - j
    sum = i * 10000 + j * 5000 + k * 1000
    if sum == Y and i + j + k == N:
      printf("{} {} {}".format(i, j, k))
      is_exist = True
      break
if is_exist == False:
  print("-1 -1 -1")

### FIXED CODE ###

def find(n, y):
  for i in range(n+1):
    for j in range(n+1-i):
      if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
        return i, j, n-i-j
  return -1, -1, -1
N, Y = map(int, input().split())
i, j, k = find(N, Y)
print("{} {} {}".format(i, j, k))
import math
a,p=map(int.input().split())
p=p+a*3
print(math.floor(p/3))

### FIXED CODE ###

import math
a,p=map(int,input().split())
p=p+a*3
print(int(math.floor(p/2)))
from copy import deepcopy
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(i)
    return ans

def check(K,N):
    while N>=K:
        if N%K == 0:
            N = N//K
        else:
            N = N%K
    if N == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)   


### FIXED CODE ###

def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def main():
    n = int(input())
    f1 = divisors(n)
    f2 = factorization(n-1)
        
    s = 1
    for f_i in f2:
        s *=(f_i[1]+1)

    for d in f1[1:]:
        t = test(n,d)
        if t==1:
            s+=1

    print(s-1)
    

def test(n,k):

    while n>=k:
        if n%k==0:
            n//=k
        else:
            n%=k
    return n



if __name__ == "__main__":
    main()
n = int(input())
blue = list()
for i in range(n):
    blue.append(input())
m = int(input())
red = list()
for j in range(m):
    red.append(input())
ans = 0
for p in range(n):
    cnt = 0
    for q in range(n):
        if blue[p] == blue[q]:
            cnt += 1
    for r in range(m):
        if blue[p] == red[r]:
            cnt -= 1
    ans = max(ans, cnt)
print(ans)

### FIXED CODE ###

a, b, c = map(int, input().split())
if a+b < c:
  print("No")
else:
  print("Yes")
import math
n,m=map(int,input().split())
print(n*m//math.gcd(n,m))


### FIXED CODE ###

def gcd(a,b):
    if a<b:
        t=a
        a=b
        b=t
    while b!=0:
            a,b=b,a%b
    return a

n,m=map(int,input().split())
print(int(n*m/gcd(n,m)))
n = int(input())
h = map(int, input().split())
count = 0
view = 0
for i in range(1, n):
    for con in h:
        if con <= h[i]:
            count += 1
    if n == count:
        view += 1
print(view)

### FIXED CODE ###

n=int(input())
lis=list(map(int,input().split()))
ans=0
 
 
for i in range(1,n):
    if max(lis[:i])<=lis[i]:
        ans+=1
 
print(ans+1)
r=range
v=input
l = [[i for i in r(1,14)] for j in r(4)]
d={"S":0,"H":1,"C":2,"D":3}
n={0:"S",1:"H",2:"C",3:"D"}
for i in r(int(v())):
    x,y = v().split()
    l[d[x]].remove(int(y))
for i in l:
    for k in i:
        print(n[i],k)

### FIXED CODE ###

r=range
v=input
l=[i+" "+str(j)for i in"SHCD" for j in r(1,14)]
for i in r(int(v())):l.remove(v())
for i in l:print(i)
a = int(raw_input())
b = int(raw_input())
print a*b, (a+b)*2

### FIXED CODE ###

a,b=map(int,raw_input().split())
print a*b,(a+b)*2
A, B, C = map(int, input().split())
if X - A <= C:
	print('YES')
else:
	print('NO')
	

### FIXED CODE ###

A, B, X = map(int, input().split())
if A+B >= X and X >= A:
	print('YES')
else:
	print('NO')
A = list(map(input().split()))
a = A[0]
b = A[1]
n = len(b)
a = int(a)
b = int(b)
jud = a*10**(n)+b
m = int(jud**.5)
if abs(m*m-jud)< 1e-6:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b = map(int,input().split())
c = a*b
if c%2==0:
  print("Even")
else:
  print("Odd")
n=int(input())
from collections import defaultdict
d=defaultdict(int)
for _ in range(n):
    s=list(input())
    s.sort()
    d[s]+=1 
ans=0
for i in d:
    ans+=d[i]*(d[i]-1)//2

print(ans)

### FIXED CODE ###

import sys
from collections import Counter

n, *S = sys.stdin.read().split()
n = int(n)

def main():
    t = [''.join(sorted(t)) for t in S]
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v*(v-1)
    print(cnt//2)

main()
A,B,C = map(int,input().split())
abc = [A,B,C]
Even = []
Odd = []
for i in range(3):
    if min(abc) == abc[i]:
        idx1 = i
    elif max(abc) == abc[i]:
        idx3 = i
    else:
        idx2 = i
    if abc[i]%2 == 0:
       Even += [i]
    else:
       Odd += [i]
       
ans = 0

if len(Even) == 3 or len(Odd) == 3:
    ans = (abc[idx3]-abc[idx2])//2 + (abc[idx3]-abc[idx1])//2
elif len(Even) == 2:
    ans += 1
    abc[Even[0]] += 1
    abc[Even[1]] += 1
    ans += (abc[idx3]-abc[idx2])//2 + (abc[idx3]-abc[idx1])//2
elif len(Odd) == 2:
    ans += 1
    abc[Odd[0]] += 1
    abc[Odd[1]] += 1
    ans += (abc[idx3]-abc[idx2])//2 + (abc[idx3]-abc[idx1])//2
    
print(ans)
    


### FIXED CODE ###

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

abc = [A,B,C]
ieven = []
iodd = []
for i in range(3):
    if abc[i] % 2 == 0:
        ieven += [i]
    else:
        iodd += [i]
        
if len(ieven) == 3 or len(iodd) == 3:
    abc.sort()
    ans = (abc[2]-abc[1])//2 + (abc[2]-abc[0])//2
else:
    if len(ieven) > len(iodd):
        abc[ieven[0]] += 1
        abc[ieven[1]] += 1
        abc.sort()
        ans = 1 + (abc[2]-abc[1])//2 + (abc[2]-abc[0])//2
    else:
        abc[iodd[0]] += 1
        abc[iodd[1]] += 1
        abc.sort()
        ans = 1 + (abc[2]-abc[1])//2 + (abc[2]-abc[0])//2
        
print(ans)
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node is None:
                    return False
                if node.data == target:
                    self.node_recreate(node)
                    return True
                elif node.data < target :
                    lst.append(node.right)
                elif node.data > target:
                    lst.append(node.left)
            return False
        
    def node_recreate(self,node):
        #ノード再作成機能を装着
        num_lst=[]
        node_lst=[node]
        while len(node_lst)>0:
            node_=node_lst.pop()
            if node_.right is not None:
                node_lst.append(node_.right)
                num_lst.append(node_.right.data)
            if node_.left is not None:
                node_lst.append(node_.left)
                num_lst.append(node_.left.data)
        node=None
        for num in num_lst:
            self.insert(num)
            
                
    
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
bst=BST(a)
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
#         bst=BST(a)#二分木も更新しないと。
#更新を削除に変更。大分計算回数は減るはず。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                bst.search(x)#削除を兼ねて
                a.remove(y)
            else:
                i+=1#これ忘れてた....sampleも通らないよ
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = Counter(a)

ans = 0
for i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)
iimport re
import functools

N = int(input())
MOD = 10 ** 9 + 7


@functools.lru_cache(maxsize=2**13)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    return ret % MOD


print(dfs(0, 'TTT'))

### FIXED CODE ###

import re

N = int(input())
memo = [{} for i in range(N+1)]
MOD = 10 ** 9 + 7


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    ret = ret % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(input().strip())
getl = lambda: input().strip()
gets = lambda: list(map(int, input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))


### FIXED CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


# fi = open('sample1.in', 'r')
# raw_input = fi.readline

H, A = gets()
if A == 1:
    print H
else:
    print(H + A - 1) / A
H, W = map(int, input().split())
matrix = []
for _ in range(H):
    row = input().split()
    matrix.append(row)
no_flag = False
for i, x in matrix:
    for j, y in matrix[i]:
        if y == '#':
            if j != 0 and matrix[i][j - 1] == '#':
                continue
            elif j != W - 1 and matrix[i][j + 1] == '#':
                continue
            elif i != 0 and matrix[i - 1][j] == '#':
                continue
            elif i != H - 1 and matrix[i + 1][j] == '#':
                continue
            else:
                no_flag = True
                break
    if no_flag == True:
        print('No')
else:
    print('Yes')

### FIXED CODE ###

H, W = map(int, input().split())
matrix = []
for _ in range(H):
    row = input()
    matrix.append(row)
no_flag = False
for i, row in enumerate(matrix):
    for j, y in enumerate(row):
        if y == '#':
            if j != 0 and matrix[i][j - 1] == '#':
                continue
            elif j != W - 1 and matrix[i][j + 1] == '#':
                continue
            elif i != 0 and matrix[i - 1][j] == '#':
                continue
            elif i != H - 1 and matrix[i + 1][j] == '#':
                continue
            else:
                no_flag = True
                break
    if no_flag == True:
        print('No')
        break
else:
    print('Yes')