Harryxun/stf_run huggingface dataset:
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
gcd_ = gcd(len(S), len(T))
saisho = len(S) * len(T) // gcd_
s_ = saisho//len(S)
t_ = saisho//len(T)

X = ["0"] * (saisho+1)
for i in range(len(S)):
    #print(i, i * s_)
    X[i * s_] = S[i]
ans = True
for i in range(len(T)):
    if X[i * t_] != "0" and T[i] != X[i * t_]:
        ans = False
    else:
        X[i * t_] = T[i]
if ans:
    print(saisho)
else:
    print("-1")
"""
ans = True
if gcd_ != 1:
    for i in range(gcd_):
        # print(i)
        if S[s_ * i] != T[t_ * i]:
            ans = False
            # break
if ans:
    print(saisho)
else:
    print(-1)
"""


### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    S=ST()
    T=ST()
    lcm = N*M//(gcd(N,M))
    ans = defaultdict(str)
    for i,s in enumerate(S):
        ans[i*lcm//N] = s
    for i,t in enumerate(T):
        if(ans[i*lcm//M] not in (t,"")):
            print(-1)
            return 
    print(lcm)
if __name__ == '__main__':
    main()
x,y,z = input()

D=int x
T=int y
S=int z

if T-D/S>= 0
    print("Yes")
  else print("No")

### FIXED CODE ###

D,T,S = map(int, input().split())

if T-D/S >= 0:
    print("Yes")
else:
    print("No")
a = sorted(map(int),input().split())
print(10*a[0]+a[1]+a[2])


### FIXED CODE ###

a = sorted(list(map(int, input().split())))
print(10*a[2]+a[1]+a[0])
import sys
input = sys.stdin.readline
a=int(input()
b=int(input()
c=int(input()
d=int(input()
print(min(a,b)+min(c,d))


### FIXED CODE ###

import sys
input = sys.stdin.readline
a=int(input())
b=int(input())
c=int(input())
d=int(input())
print(min(a,b)+min(c,d))
from fractions import gcd

N,M=map(int,input().split())
#List=list(map(lambda x:int(x)/2,input().split()))
List=list(int,input().split()))


LCM=1
cut2count=0
a=List[0]
while a%2==0:
    a/=2
    cut2count+=1

for i in List:
    i/=2
    LCM*=i/gcd(LCM,i)
        
    cut2countb=0
    b=i
    while b%2==0:
        b/=2
        cut2count+=1
    if cut2count!=cut2countb:
        print(0)
        exit()


#for i in List:
 #   if LCM/i%2==0:
  #      print(0)
   #     exit()

print(int(M//(LCM*2)+M%(LCM*2)//LCM))


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()
N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
    print(A)
                    
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

S =[0]*(N + 1)
S[0] = 1
if A[0] == 1:
    S[1] = 0
else:
    S[1] = 1

for i in range(2, N+1):
    if i in A:
        S[i] = 0
    else:
        S[i] = (S[i-1] + S[i-2]) % 1000000007
print(S[N])


### FIXED CODE ###

N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(N + 1)]
DP[0] = 1
if 1 in A:
    DP[1] = 0
else: DP[1] = 1
for i in range(2, N+1):
    if i in A:
        DP[i] = 0
    else:
        DP[i] = (DP[i-1] + DP[i-2])%p
print(DP[N])
m = 9
l = []
r = []
for i in range(5):
  a = int(input())
  if a % 10 != 0:
    m = 10 - a % 10
    b = a + a % 10
    l.append(b)
    r.append(m)
  else:
    l.append(a)
r.sort()
print(sum(l) - r[-1])
      

### FIXED CODE ###

m = 9
l = []
r = []
for i in range(5):
  a = int(input())
  if a % 10 != 0:
    m = 10 - a % 10
    b = a + m
    l.append(b)
    r.append(m)
  else:
    l.append(a)
    r.append(0)
r.sort()
print(sum(l) - r[-1])
N, K = list(map(int, input().split()))
x = 0
if N%2:
  x = N/2
else:
  x = (N-1) / 2
return K<=x

### FIXED CODE ###

N, K = [int(s) for s in input().split(' ')]
x = 0
if N%2:
    x = (N + 1) / 2
else:
    x = N/ 2
if x>=K:
    print("YES")
else:
    print("NO")
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N + 1)]
        self.friendcount = [1] * (N + 1)

    def getroot(self, x):
        node = self.root[x]
        if node == x:
            return x
        self.root[x] = self.getroot(node)
        return self.root[x]

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        self.root[xroot] = yroot
        self.friendcount[yroot] += self.friendcount[xroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x) # only root has an accurate number
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))


### FIXED CODE ###

class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.friendcount = [1] * N

    def getroot(self, x):
        node = self.root[x]
        if node == x:
            return x
        self.root[x] = self.getroot(node)
        return self.root[x]

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x)
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6 + 10 # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

k=int(input())
s=input()
lens=len(s)
mod=10**9+7
ans=0

now=1

for i in range(k+1):
    ans+=pow(25,i,mod)*pow(26,k-i,mod)*cmb(lens+i-1,lens-1,mod)
    ans=ans%mod

print(ans)

### FIXED CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10 # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

k=int(input())
s=input()
lens=len(s)
mod=10**9+7
ans=0

now=1

for i in range(k+1):
    ans+=pow(25,i,mod)*pow(26,k-i,mod)*cmb(lens+i-1,lens-1,mod)
    ans=ans%mod

print(ans)
n = int(input())
k = int(input())
l = []
for i in range(n):
 l.append(int(input()))
ans = 0
for i in l:
 if( i < abs( i - k )  ):
  ans += 2*abs(i-k)
 else:
  ans += 2*i
print(ans)


### FIXED CODE ###

n = int(input())
k = int(input())
l = input().split()
ans = 0
for i in l:
  j = int(i)
  if( j < abs( j - k )  ):
    ans += 2*j
  else:
    ans += 2*abs(j-k)
print(ans)
A,B,X = map(int,input().split())
print("Yes" if A < X and (A+B) > x else "No")

### FIXED CODE ###

A,B,X = map(int,input().split())
print("YES" if A <= X <=(A+B) else "NO")
from itertools import accumulate

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

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = list([0]+accumulate(expP)) # 0を忘れずに
print(acc)

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)

### FIXED CODE ###

from itertools import accumulate

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

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = [0]+ list(accumulate(expP)) # 0を忘れずに

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
import math
# 最小公倍数
def lcm(x, y):
    return (x * y) // math.gcd(x, y)    
a, b, c, d = map(int, input().split())
e = lcm(c, d)
#print("e: {}".format(e))
#print("c: {} - {}".format(b // c, (a - 1) // c))
#print("d: {} - {}".format(b // d, (a - 1) // d))
#print("e: {} - {}".format(b // e, (a - 1) // e))
count_c = b // c - (a - 1) // c
count_d = b // d - (a - 1) // d
count_e = b // e - (a - 1) // e
# b - a の中から d の倍数の個数を取得
#print("count_c: {}".format(count_c))
#print("count_d: {}".format(count_d))
#print("count_e: {}".format(count_e))
print(b - a + 1 - (count_c + count_d - count_e))

### FIXED CODE ###

import fractions
# 最小公倍数
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)    
a, b, c, d = map(int, input().split())
e = lcm(c, d)
#print("e: {}".format(e))
#print("c: {} - {}".format(b // c, (a - 1) // c))
#print("d: {} - {}".format(b // d, (a - 1) // d))
#print("e: {} - {}".format(b // e, (a - 1) // e))
count_c = b // c - (a - 1) // c
count_d = b // d - (a - 1) // d
count_e = b // e - (a - 1) // e
# b - a の中から d の倍数の個数を取得
#print("count_c: {}".format(count_c))
#print("count_d: {}".format(count_d))
#print("count_e: {}".format(count_e))
print(b - a + 1 - (count_c + count_d - count_e))
import sys
n, a, b = map(int, sys.stdin.readline().split())
balls = n // (a+b) * a
if n % (a+b) <= a:
  balls += n % (a+b)
else:
  balls += a
print(balls)


### FIXED CODE ###

s = input()
if s == 'AAA' or s == 'BBB':
  print('No')
else:
  print('Yes')
n = int(input())

a = list(map(int, input().split()))
s = 10000000

for i in range(2+max(a)):
  s_tmp = 0
  
  for j in range(n):
    s_tmp = s_tmp + abs(a[l] - i - (j+1))
    
    if s_tmp < s:
      s = s_tmp

print(s)

### FIXED CODE ###

n = int(input())

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

sorted_num = sorted([a[i] - i for i in range(len(a))])

b = sorted_num[len(sorted_num)//2]
print(sum([abs(b-i) for i in sorted_num]))
N,M = map(int,input().split())
def gcd(a,b):
    if a >= b:
        if b == 0:
            return a
        else:
            return gcd(b,a%b)
    else:
        if a == 0:
            return b
        else:
            return gcd(a,b%a)
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    flag = True
    L = int((N//gcd(N,M))*M)
    m = L//M
    n = L//N
    for i in range(min(N,M)):
        if i*m <= N-1 and i*n <= M-1:
            if S[i*m*L//N] != T[i*n*L//M]:
                flag = False
                break
    if flag:
        print(L)
    else:
        print(-1)


### FIXED CODE ###

N,M = map(int,input().split())
def gcd(a,b):
    if a >= b:
        if b == 0:
            return a
        else:
            return gcd(b,a%b)
    else:
        if a == 0:
            return b
        else:
            return gcd(a,b%a)
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    flag = True
    L = int((N//gcd(N,M))*M)
    m = L//M
    n = L//N
    for i in range(max(N,M)):
        if i*m <= N-1 and i*n <= M-1:
            if S[i*m] != T[i*n]:
                flag = False
                break
    if flag:
        print(L)
    else:
        print(-1)
N = int(input())
t = list(input())
Ans = ['n' for _ in t]

def judge(prevSW, SW, ox):
    if SW == 'S':
        if ox == 'o':
            return prevSW
        else:
            if prevSW == 'S':
                return 'W'
            else: return 'S'
    elif SW == 'W':
        if ox == 'x':
            return prevSW
        else:
            if prevSW == 'S':
                return 'W'
            else: return 'S'

def decideorder(startSW):
    Ans[1] = startSW
    for i in range(2,N):
        Ans[i] = judge(Ans[i-2], Ans[i-1], t[i-1])


Ans[0] = 'S'
decideorder('S')
if judge(Ans[-1], Ans[0], t[0]) is Ans[0]:
    print("".join(Ans))
else:
    decideorder('W')
    if judge(Ans[-1], Ans[0], t[0]) is Ans[0]:
        print("".join(Ans))
    else:
        Ans[0] = 'W'
        decideorder('S')
        if judge(Ans[-1], Ans[0], t[0]) is Ans[0]:
            print("".join(Ans))
        else:
            decideorder('W')
            if judge(Ans[-1], Ans[0], t[0]) is Ans[0]:
                print("".join(Ans))
            else:
                print(-1)

### FIXED CODE ###

N = int(input())
dis = (N//15)*200
print(N*800-dis)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate

fact = [1]

for i in range(1, 2 * 10 ** 3 + 1):
    fact.append(fact[-1] * i)


def comb(n, r):
    return int(fact[n] / fact[r] / fact[n-r])


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

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += comb(nums[b], 3)
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += comb(nums[b], 2) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from bisect import bisect_left


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

    l.sort()

    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            a = l[i]
            b = l[j]
            mx = bisect_left(l, a + b)
            ans += mx - j - 1

    print(ans)


if __name__ == "__main__":
    main()
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

table = [[0]*max(M)]*n

def solve(i, m): 
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != 0:
        return table[i][m]
    else:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

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

table = [[-1 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != -1:
        return table[i][m]
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res
    else:
        res = solve(i + 1, m)
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
s = input()
s = s.replace(s[0],'')
s = s.replace(s[0],'')
if len(s) == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
s = input()
s = s.replace(s[0],'')
if len(s) == 0:
    print('No')
    sys.exit()
else:
    s = s.replace(s[0],'')
if len(s) == 0:
    print('Yes')
else:
    print('No')
s = input()
n = int(s) // 2019
a = [i*2019 for i in range(1, n+1)]
ans=0
for j in a:
  if j in s:
    ans += 1
print(ans)

### FIXED CODE ###

s=input()[::-1]
ans=0
u=0
d=1
l=[0]*2019
l[0]=1
for i in map(int,s):
  u=(u+i*d)%2019
  l[u]+=1
  d=d*10%2019
for i in l:
  ans+=i*(i-1)//2
print(ans)
n=int(input())
array=list(map(int,input().split()))
list2=[]
for i in range(n-1):
  for j in range(i+1,n):
    list2.append(array[i]*array[j])
a=n*(n-1)/2
ans=0
for m in range(a):
  ans=ans+list2[m]
  if ans>=10**9+7:
    ans=ans-(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=sum(a)*sum(a)
for i in range(n):
  ans-=a[i]*a[i]
ans//=2
mod=10**9+7
ans%=mod
print(ans)
#わからないのでギブアップコピペ
h,w=map(int,input().split())

a=[] #入力データのリスト化
for i in range(h):
  x=input().split()
  a.append(x)

h1=[]
for i in range(h):
  if a[i]==['.']*w:
    h1.append(i)

w1=[]
for i in range(w):
  flag=0
  for j in range(h):
    if a[j][i]=='#':
      flag=1
      break
  if flag==0:
    w1.append(i)

ans=[]
for i in range(h):
  if i not in h1:
    r=[]
    for j in range(w):
      r.append(a[i][j])
    ans.append(r)

for i in range(lens(ans)):
  print(''.join(ans[i]))

### FIXED CODE ###

#全然わからず完コピ
H,W=map(int,input().split())
a=[list(input()) for _ in range(H)]
h=[]
for i in range(H):
  if a[i]==['.']*W:
    h.append(i)

w=[]
for i in range(W):
  flag=0
  for j in range(H):
    if a[j][i]=='#':
      flag=1
      break
  if flag==0:
    w.append(i)
  
ans=[]
for i in range(H):
  if i not in h:
    r=[]
    for j in range(W):
      if j not in w:
        r.append(a[i][j])
    ans.append(r)

for i in range(len(ans)):
  print("".join(ans[i]))
n, k, m = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) + k < n * m:
  ans = -1
else :
  ans = n * m - sum(a)
  if ans < 0:
    ans = 0
print(ans)

### FIXED CODE ###

x = input()
ans = ord(x) + 1
print(chr(ans))
if a >= 3200:
  print(s)
else:
  print('red')

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
  print(s)
  
else:
  print("red")
H=input()
W=input()
h=input()
w=input()

H=int(H)
W=int(W)
h=int(h)
w=int(w)

print(HW-wH-hH-wh)

### FIXED CODE ###

a,b = map(int,input().split())
c,d = map(int,input().split())
print((a-c)*(b-d))
import sympy
x=int(input())
r=sympy.nextprime(50)
print(r)


### FIXED CODE ###

x = int(input())
while any(x % i < 1 for i in range(2, x)): 
    x += 1
print(x)
n,l=map(int,input().split())
t=[]
p=[]
for i in range(n):
    t.append(l+i)
    if l+i>=0:
        p.append(l+i)
if p=[]:
    print(sum(t)-max(t))
else:
    print(sum(t)-min(p))


### FIXED CODE ###

n,l=map(int,input().split())
t=[]
p=[]
for i in range(n):
    t.append(l+i)
    if l+i>=0:
        p.append(l+i)
if p==[]:
    print(sum(t)-max(t))
else:
    print(sum(t)-min(p))
a=[]
for i in range(3):
    a.append(list(map(int,input().split())))
b=[[0 for i in range(3)] for j in range(3)]
n=int(input())
for i in range(n):
    p=int(input())
    for j in range(3):
        for k in range(3):
            if p==a[i][j]:
                b[i][j]=1
for i in range(3):
    x=0
    y=0
    for j in range(3):
        if b[i][j]==1:
            x+=1
        if b[j][i]==1:
            y+=1
    if x==3 or y==3:
        print('Yes')
        exit()
if b[0][0]==b[1][1]==b[2][2]==1:
    print('Yes')
    exit()
if b[2][0]==b[1][1]==b[0][2]==1:
    print('Yes')
    exit()
print('No')

### FIXED CODE ###

a=[]
for i in range(3):
    a.append(list(map(int,input().split())))
b=[[0 for i in range(3)] for j in range(3)]
n=int(input())
for i in range(n):
    p=int(input())
    for j in range(3):
        for k in range(3):
            if p==a[j][k]:
                b[j][k]=1
for i in range(3):
    x=0
    y=0
    for j in range(3):
        if b[i][j]==1:
            x+=1
        if b[j][i]==1:
            y+=1
    if x==3 or y==3:
        print('Yes')
        exit()
if b[0][0]==b[1][1]==b[2][2]==1:
    print('Yes')
    exit()
if b[2][0]==b[1][1]==b[0][2]==1:
    print('Yes')
    exit()
print('No')
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


sys.setrecursionlimit(10 ** 7)

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

MAGIC = []
for _ in range(N):
    a, b = map(int, input().split())
    MAGIC.append((a, b))

dp = [[10**9] * (H+1) for _ in range(N+1)]

for i in range(N):
    dp[i][0] = 0


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            m = min(dp[i+1][h-MAGIC[i][0]:])
            #print("num", h-MAGIC[i][0], dp[i][h-MAGIC[i][0]:])
            # print(m)
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            #print("ok", h)
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])

    # print(dp[i+1])

# print(dp)
print(dp[N][H])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

MAGIC = []
for _ in range(N):
    a, b = map(int, input().split())
    MAGIC.append((a, b))

INF = 10 ** 10
dp = [INF] * 20000
dp[0] = 0

for i in range(N):
    for h in range(H):
        a, b = MAGIC[i]

        if dp[h+a] > (dp[h] + b):
            dp[h+a] = dp[h] + b

print(min(dp[H:]))