Harryxun/stf_run huggingface dataset:
import math

N, Ma, Mb = map(int,input().split())
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    MA += a[i]
    MB += b[i]

dp = [[[math.inf for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != math.inf:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]

ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        print(a,b,dp[N][a][b])
        if a/b == rate and dp[N][a][b] != math.inf:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min([dp[N][a][b], ans])
print(ans)


### FIXED CODE ###


N, Ma, Mb = map(int,input().split())
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
MC = 0
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    MA += a[i]
    MB += b[i]
    MC += c[i]
    
dp = [[[MC for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != MC:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
                else:
                    dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]

ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        if a/b == rate and dp[N][a][b] != MC:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min(dp[N][a][b], ans)
print(ans)
N,M = map(int,input().split())
A = [[] for i in range(N+1)]

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in L[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d :
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

print(ans)

### FIXED CODE ###

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

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in A[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

print(ans)
S = input()

if S[0] == S[1] = S[2]:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

S = input()

if S[0] == S[1] == S[2]:
  print('No')
else:
  print('Yes')
def main():
    n = int(input())
    a = [int(input) for i in range(n)]
    ans = sum(a)
    if(ans % 2 == 0):
        print('second')
    else:
        print('first')

main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list([(int(input())) % 2 for i in range(n)])
    ans = sum(a)
    if(ans == 0):
        print('second')
    else:
        print('first')

main()
import math
import sys

sys.setrecursionlimit(100000000)
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        p = 1/(N-i)
        return dfs(i+1, x % S[i]) * p + dfs(i+1, x) * (1-p)


print((int(dfs(0, X) * math.factorial(N))) % (10**9+7))

### FIXED CODE ###

import math
import sys

sys.setrecursionlimit(100000000)
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        return dfs(i+1, x % S[i]) + dfs(i+1, x) * (N-i-1)


print(dfs(0, X) % (10**9+7))
def main():
    n,k=map(int,input().split())
    a=[0]*n
    for i in range(k):
        d=int(input())
        tmp=input()
        for j in range(d):
            a[int(tmp[j*2])-1]+=1
    ans=0
    for i in range(n):
        if a[i]==0:
            ans+=1
    print(ans)

if __name__ =='__main__':
    main()

### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    a=[0]*n
    for i in range(k):
        d=int(input())
        if d==1:
            a[int(input())-1]+=1
        else:
            tmp=list(map(int,input().split()))
            for j in tmp:
                a[j-1]+=1
    ans=0
    for i in range(n):
        if a[i]==0:
            ans+=1
    print(ans)

if __name__ =='__main__':
    main()
N, T = map(int, input().split())

l = []

for i in range(N):
    a = list(map(int, input().split()))
    if T >= a[1]:
        l.append(a[0])

print('TLE' if len(l) == 0 else min(l))

### FIXED CODE ###

n = int(input())
if n == 1:
    print('Hello World')
else:
    a, b = [int(input()) for _ in range(2)]
    print(a+b)
from sys import stdin
 
x,y,z = stdin.readline().split()

print (int(x)-int(z))/(int(y)+int(z))


### FIXED CODE ###

from sys import stdin
import math
 
x, y, z = stdin.readline().split()
 
print (math.floor(( ( int(x)-int(z) ) / ( int(y) + int(z) ) )))
a,b,c = list(map(int,input().split()))
temp = 0 
if a > b:
        temp = a
	a = b
	b = temp
if b > c:
	temp = b
	b = c
	c = temp
if a > b:
	temp = a
	a = b
	b = temp
print(a,b,c)

### FIXED CODE ###

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

num.sort()

print(num[0], num[1], num[2])
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [1 if is_prime[x] and is_prime[(x+1)//2] else 0 for i in range(0,100001) ]

for i in range(1,100001):
    like2017[i] += like2017[i-1]
for i in range(q):
    l,r = map(int, input().split())
    print(like2017[r]-like2017[l-1])


### FIXED CODE ###

import numpy as np
n=123456
q = int(input())
 
is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
 
cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]
 
for i in range(1,n+1):
    cnt[i]+=cnt[i-1]
 
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])
while True:
    C = input()
    if C == "-":
        break
    count = int(input())
    shuffle = [int(input() for i in range(count))]
    for h in shuffle:
        C = C[h:] + C[:h]
    print(C)

### FIXED CODE ###

while True:
    C = input()
    if C == "-":
        break
    count = int(input())
    shuffle = [int(input()) for i in range(count)]
    for h in shuffle:
        C = C[h:] + C[:h]
    print(C)
n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

r = [[] for _ in range(n)]

for u, v, w in uvw:
    r[u-1].append([v-1, w])
    r[v-1].append([u-1, w])

def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1
    #print(count)

c[0] = 0
f(0)

for x in c:
    print(x)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)

n = int(input())
uvw = [tuple(int(x) for x in input().split()) for _ in range(n-1)]

c = [-1] * n

r = [[] for _ in range(n)]

for u, v, w in uvw:
    r[u-1].append([v-1, w])
    r[v-1].append([u-1, w])

def f(p):
    count = 0
    for x, w in r[p]:
        if c[x] == -1:
            if w % 2 == 0:
                c[x] = c[p]
                f(x)
            else:
                c[x] = (c[p] + 1) % 2
                f(x)
            count += 1
    #print(count)

c[0] = 0
f(0)

for x in c:
    print(x)
N, D = map(int, input().split())

if N % (2*D + 1) == 0:
  print(N // (2*D + 1))
else:
  print(N // (2*D + 1) + 1)


### FIXED CODE ###

r = int(input())
d = 3*(r**2)
print(d)
from collections import deque

n, m = map(int, input().split()) #ノード数, エッジ数
x = [] #エッジ
y = {i + 1 for i in range(n)} #未探索ノード
z = deque([1]) #探索用キュー
ans = []

for i in range(m):
    x += [set(map(int, input().split()))]

while y != set():
    s = set()
    t = z.popleft()
    for u in x:
        if t in u:
            s.add((u - t).pop())
    for v in s & y:
        ans[v - 1] = t
        z.append(v)
    y.remove(t)

print('Yes')
for w in ans[1:]:
    print(w)


### FIXED CODE ###

# 入力
N, M = map(int, input().split()) # ノード数, エッジ数
edges = [[] for i in range(N)] # エッジ
for i in range(M):
    A, B = map(int, input().split())
    edges[A - 1] += [B - 1]
    edges[B - 1] += [A - 1]

# 幅優先探索
que = [0] # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ
while -1 in ans: # 未探索ノードがある間
    quetmp = que
    que = []
    for node in quetmp: # 探索キュー内のノードに対して
        for neighbor in edges[node]: # 全ての隣接ノードに対して
            if ans[neighbor] == -1: # 未探索なら
                ans[neighbor] = node + 1 # 道しるべを設定
                que += [neighbor] # キューに入れる

# 出力
print('Yes')
for a in ans[1:]:
    print(a)
K = int(input())
S = input()

if len(S) =< K:
 print(S)
else:
 print(S[1:K+1]+'...')


### FIXED CODE ###

K = int(input())
S = input()
if len(S) <= K:
 print(S)
else:
 print(S[:K] + '...')
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a.sort()
bc = []
for _ in range(m):
    bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=lambda x: x[1], reverse=True)
idx = 0
for i in range(m):
    v = bc[i][1]
    for j in range(idx, idx + bc[i][0]):
        if a[j] < v:
            a[j] = v
        else: break
        if j == idx + bc[i][0] - 1: idx += bc[i][0]
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
bc = []
for _ in range(m): bc.append([int(i) for i in input().split()])
a.sort()
bc.sort(key=lambda x:x[1])
bc = bc[::-1]
idx = 0
for b, c in bc:
    for bi in range(b):
        if idx + bi == n or a[idx+bi] >= c:
            idx = "e"
            break
        else: a[idx+bi] = c
    if idx == "e": break
    else: idx += b
print(sum(a))
hon = [2,4,5,7,9]
pon = [0,1,6,8]
bon = [3]
if int(n[-1]) in hon:
    print('hon')
elif int(n[-1]) in pon:
    print('pon')
else:
    print('bon')

### FIXED CODE ###

n = str(input())
hon = [2,4,5,7,9]
pon = [0,1,6,8]
bon = [3]
if int(n[-1]) in hon:
    print('hon')
elif int(n[-1]) in pon:
    print('pon')
else:
    print('bon')
n = int(input())
s = list(map(str,input().split()))
if s in 'Y':
  print('Four')
else:
  print('Three')

### FIXED CODE ###

n = int(input())
s = map(str,input().split())
if 'Y' in s:
  print('Four')
else:
  print('Three')
x, a, b = map(int, input().split())
if abs(a-x) < abs(b-x):
  print('A')
elif:
  print('B')

### FIXED CODE ###

x, a, b = map(int, input().split())
if abs(a-x) < abs(b-x):
  print('A')
else:
  print('B')
(a,b) = input().rstrip().split(' ')
#a = int(a)
#b = int(b)

#以下でも代替可
(a,b) = [int(x) for x in input().rstrip().split(' ')]

if a < b:
 print("a < b")
elif a > b:
 print("a > b")
else:
 print("a == b")

### FIXED CODE ###

#(a,b) = input().rstrip().split(' ')
#a = int(a)
#b = int(b)

#以下でも代替可
(a,b) = [int(x) for x in input().rstrip().split(' ')]

if a < b:
 print("a < b")
elif a > b:
 print("a > b")
else:
 print("a == b")
import sys
import math

n = int(input())
a = list(map(int, input().split()))
sosu = a[:]

for i in range(2, n//2):
  for j in range(2,n):
    if i*j > n:
      break
    else:
      sosu.remove(i*j) 

m = 0

for i in sosu:
  if i > n/2:
    m = sosu.index(i)
    break

del sosu[:(m-1)]

newa = [i for i in a if i not in sosu]

for i in newa:
  if i != newa[0]:
    print('-1')
    sys.exit()

num = [str(i+1) for i, x in enumerate(a) if x == 1]

if len(num) == 0:
  print('0')
else:
  print(len(num))
  num = ' '.join(num)
  print(num)

### FIXED CODE ###

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

ball = [0 for i in range(n)]

for i in reversed(range(n)):
  if n//2 < i:
    ball[i] = a[i]
  else:
    if (sum(ball[i::(i+1)]) - a[i]) % 2 == 0:
      ball[i] = 0
    else:
      ball[i] = 1


num = [str(i+1) for i, x in enumerate(ball) if x == 1]

if len(num) == 0:
  print('0')
else:
  print(len(num))
  num = ' '.join(num)
  print(num)
a, b = map(int, input().split())
if a == b:
    print("EQUAL")
elif a > b:
    print("GREATER")
else:
    print("LESS")

### FIXED CODE ###

a = int(input())
b = int(input())
if a == b:
    print("EQUAL")
elif a > b:
    print("GREATER")
else:
    print("LESS")
t,x=map(int,input().spllit());pirnt(t/x)

### FIXED CODE ###

t,x=map(int,input().split());print(t/x)
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

N,M=map(int, input().split())
for _ in range(M):
    f=0
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)
chk=[0]*N
chk[0]=1
temp=1
a=0
while a<N:
    for i in range(len(d[temp])):
        chk[d[temp][i]-1]=1
        d[temp].append(d[temp][i])
        q.append(d[temp][i])

    if len(q)>0:
        while a<N:
            if chk[a]==0:
                chk[a]=1
                temp=a+1
                break
            a+=1
    else:
        temp=q.pop()

ans=0
for i in  range(N):
    ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

for _ in range(M):
    A,B=map(int, input().split())
    union(A,B)

print(max(rank))
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = sum(X) + 1

    dp = [[[0] * MAX for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        x = X[i - 1]
        for j in range(n):
            for k in range(MAX):
                dp[i][j][k] += dp[i - 1][j][k]
                if k + x < MAX:
                    dp[i][j + 1][k + x] += dp[i - 1][j][k]
    res = 0
    for j in range(1, n + 1):
        res += dp[-1][j][a * j]
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = n * a
    dp = [[[0] * (MAX + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        x = X[i - 1]
        for k in range(n):
            for s in range(MAX):
                dp[i][k][s] += dp[i - 1][k][s]
                if s + x <= MAX:
                    dp[i][k + 1][s + x] += dp[i - 1][k][s]
    res = 0
    for k in range(1, n + 1):
        res += dp[-1][k][a * k]
    print(res)


if __name__ == '__main__':
    resolve()
l = list(map(int,input().split()))
N = l[0]
A = l[1] 
B = l[2]
C = l[3]
D = l[4]
S = input()
S_list = list(S)

if B < C < D :
    count = 0
    for i in range(A, D-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    if count >= 1:
        print('No')
    else : 
        print('Yes')
elif C < B < D :
        count = 0
    for i in range(A, C-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    for i in range(B, D-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    if count >= 1:
        print('No')
    else :
        print('Yes')
elif B < D < C
    count = 0
    for i in range(A, C-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    if count >= 1:
        print('No')
    count = 0
    for i in range(B-2, D-1):
        if S_list[i] == S_list[i+1] == S_list[i+2] == '.' :
            count += 1
    if count >= 1:
        print('Yes')  
    else:
        print('No') 


### FIXED CODE ###

l = list(map(int,input().split()))
N = l[0]
A = l[1] 
B = l[2]
C = l[3]
D = l[4]
S = input()
S_list = list(S)

if B < C < D :
    count = 0
    for i in range(A, D-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    if count >= 1:
        print('No')
    else : 
        print('Yes')
elif C < B < D :
    count = 0
    for i in range(A, C-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1
    for j in range(B, D-1):
        if S_list[j] == S_list[j+1] == '#' :
            count += 1
    if count >= 1:
        print('No')
    else :
        print('Yes')
elif B < D < C:
    count = 0
    for i in range(A, C-2):
        if S_list[i] == S_list[i+1] == '#' :
            count += 1

    cou = 0
    for i in range(B-2, D-1):
        if S_list[i] == S_list[i+1] == S_list[i+2] == '.' :
            cou += 1
    if cou >= 1 and count < 1 :
        print('Yes')  
    else:
        print('No')
n = int(input())
a = list(map(int, input().split()))

count = 0
while all(i % 2 == 0 for i in a):
    a = [i / 2 for i in a]
    count += 1
print(count)

### FIXED CODE ###

i = input()
print(i.count("1"))
import numpy as np

C = np.charray(input(),input(),input())

print(C[0][0],C[1][1],C[2][2])

### FIXED CODE ###

 
C_0=list(input())
C_1=list(input())
C_2=list(input())

# D = C[0][0]+C[1][1]+C[2][2]
# print(str(D))
print(C_0[0]+C_1[1]+C_2[2])
def solve():
    n,m,k = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    arr1 = list(map(int,input().split()))
    count = 0
    trackLoop = 1
    trackCount = 0
    while trackCount<k:
        if trackCount==k:
            return count+1
        if len(arr)>0 and arr[0]<arr1[0]:
            trackCount+=arr.pop(0)
        else:
            if len(arr1)>0:
                trackCount+=arr1.pop(0)
            else:
                trackCount+=arr.pop(0)
        if trackCount==k:
            return count+1
        trackLoop+=1
        count+=1
        
    return count-1
    
print(solve())

### FIXED CODE ###

def solve():
    n,m,k = list(map(int,input().split()))
    arr = list(map(int, input().split()))
    arr1 = list(map(int, input().split()))
    aTrack = 0
    bTrack = sum(arr1)
    Bn = len(arr1)
    ans = 0
    for An in range(len(arr)+1):
      if An>0:
        aTrack += arr[An-1]
      if aTrack>k:
        break
      while aTrack+bTrack>k:
        Bn -= 1
        bTrack -= arr1[Bn]
      ans = max(ans, An+Bn)
    print(ans)
    
            
solve()
# coding: UTF-8
inputs=[]
for i in range(1,10):
    inputs.append(input())
inputs.sort(reverse=True)
for i in range(0,3):
    print x[i]

### FIXED CODE ###

# coding: UTF-8
inputs=[]
for i in range(0,10):
    inputs.append(input())
inputs.sort(reverse=True)
#print "\n"
for i in range(0,3):
    print inputs[i]
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

N,M = map(int,input().split())
S = str(input())
T = str(input())

L = lcm(N,M)
if L == max(N,M):
  L *= 2
X = [""]*(L+10**5)
if S[0] != T[0]:
  print(-1)
  exit()
else:
  X[0] = S[0]

for i in range(1,N):
  X[i*L//N] = S[i]
for j in range(1,M):
  if X[j*L//M] == "" or X[j*L//M] == T[j]:
    pass
  else:
    print(-1)
    exit()

print(L)

### FIXED CODE ###

import math
 
N,M = map(int,input().split())
S = list(str(input()))
T = list(str(input()))
g = math.gcd(N,M)
gn,gm = N//g,M//g
for i in range(g):
  if S[i*gn] != T[i*gm]:
    print(-1)
    exit()

print(gn*gm*g)
import heapq

N, K = map(int, input().split(" "))
 
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))


max_points = []
heapq.heapify(max_points)
for start_point in range(1, N+1):
    flg = False
    C_point = 0
    max_point = []
    heapq.heapify(max_point)
    now_point = start_point
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        
        heapq.heappush(max_point, -C_point)
#        max_point.append(C_point)
        now_point = next_point
    
        if next_point == start_point:
            flg = True
            l = _ + 1
            last_point = C_point
            break
        
    if flg:
#        print("l",l)
        q, r = divmod(K, l)
#        print(q,r)
        now_point = start_point
        C_point = 0
        for _ in range(r):
            next_point = Ps[now_point-1]
            C_point += Cs[next_point-1]
            ins = last_point * q + C_point
            heapq.heappush(max_point, -ins)
#            max_point.append(ins)
            
            now_point = next_point        
#    print("2nd", max_point)
    max_point_ = heapq.heappop(max_point)
    heapq.heappush(max_points, max_point_)
#    max_points.append(max(max_point))
    
print(-heapq.heappop(max_points))
#print(max(max_points))

### FIXED CODE ###

import re

S = input()

rrr = S.count("RRR")
rr = S.count("RR")
r = S.count("R")

if rrr == 1:
    print(3)
elif rr == 1:
    print(2)
elif r == 1 or r == 2:
    print(1)
else:
    print(0)
s = input()
t = input()

def match(s1, s2):
    if len(s1) < len(s2):
        return False
    for i, j in zip(s1, s2):
        if i != j and i != "?":
            return False
    return True

result = []
for i in range(50):
    if match(s[i:], t):
        result.append((s[:i] + t + s[i + len(t):]).replace("?", "a"))
result.sort()
print(result[0])


### FIXED CODE ###

s = input()
t = input()

def match(s1, s2):
    if len(s1) < len(s2):
        return False
    for i, j in zip(s1, s2):
        if i != j and i != "?":
            return False
    return True

result = []
for i in range(50):
    if match(s[i:], t):
        result.append((s[:i] + t + s[i + len(t):]).replace("?", "a"))
result.sort()
if not result:
    print("UNRESTORABLE")
else:
    print(result[0])
S = input()
a = True
for i in range(len(S)):
    if len(S)%2==0 :a=False break
    else:
        if S[i/2] != 'h' or S[i/2 +1] !- 'i':
            a=False
            break

if a: print('Yes')
else : print('No')
        
        

### FIXED CODE ###

S = input()
a = True
for i in range(len(S)):
    if len(S) % 2 != 0:
        a = False 
        break
    else:
        if i %2==0 and (S[i] != 'h' or S[i+1] != 'i'):
            a = False

if a: 
    print('Yes')
else: 
    print('No')