Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((W+1,N+1), dtype=int)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(wv)
    #print(dp)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            print(i,j)
            print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()
N = int(input())
a = [0 for i in range(N)]
chain = [0 for i in range(N)]
for i in range(N):
  a[i] = int(input())
  chain[a[i]] = chain[a[i]-1]+1
print(max(chain))

### FIXED CODE ###

N = int(input())
a = [0 for i in range(N)]
chain = [0 for i in range(N+1)]
for i in range(N):
  a[i] = int(input())
  chain[a[i]] = chain[a[i]-1]+1
print(N-max(chain))
n = int(input())
a = [int(i) for i in input().split()]
ans = 1
for i in a:
  ans = ans * i
  if ans >= 1000000000000000000:
  	break:

if ans >= 1000000000000000000:
    print('-1')
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 1
if 0 in a:
  print(0)
else:
  for i in a:
    ans = ans * i
    if ans > 1000000000000000000:
  	  break
  if ans > 1000000000000000000:
    print('-1')
  else:
    print(ans)
S = input()

Slen = len(S)
center = int(Slen/2)

Answer = 0

a = S[:center]
if center%2 == 0:
  b = S[-1:center-1:-1]
else:
  b = S[-1:center:-1]

for i in range(len(a)):
  if a[i] != b[i]:
    Answer += 1

print(Answer)

### FIXED CODE ###

S = input()

Slen = len(S)
center = int(Slen/2)

Answer = 0

a = S[:center]
b = S[-1:center-1:-1]

for i in range(len(a)):
  if a[i] != b[i]:
    Answer += 1

print(Answer)
import fractions

n,x = map(int,input().split())

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


if n == 1:
  print(abs(L[0]-x))
else:
  L.append(x)
  L = sorted(L)
  a = L[1]-L[0]
  for i in range(n-2):
    b = L[i+2]-L[i+1]
    a = fractions.gcd(a,b)
print(a)


### FIXED CODE ###

import fractions

n,x = map(int,input().split())

L = list(map(int,input().split()))
y = []
for i in range(n):
  y.append(abs(L[i]-x))
tmp = y[0]

for i in range(n-1):
  tmp = fractions.gcd(tmp,y[i+1])
print(tmp)
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

l = [0]*(X*Y*Z)
c = 0

from decimal import *

for x in range(X):
  for y in range(Y):
    for z in range(Z):
      l[c] = Decimal(A[x]+B[y]+C[z])
      c += 1

ans = sorted(l,reverse = True)

for k in range(K):
  print(ans[k])

### FIXED CODE ###

from heapq import *
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = sorted(A,reverse = True)
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

cake = []
heapify(cake)
for x in range(X):
  for y in range(min(Y,K//(x+1)+1)):
    for k in range(min(Z,K//((x+1)*(y+1))+1)):
      heappush(cake,-(A[x]+B[y]+C[k]))
for _ in range(K):
  print(abs(heappop(cake)))
N=input(':')

K=input(':')

N=int(N)

K=int(K)

if N%K==0 :
    print(0)

else :
    print(1)

### FIXED CODE ###

N,K = map(int,input().split())
if N%K == 0:
  print(0)
else :
  print(1)
l = input().split(" ")
j = input().split(" ")
k = int(l[0])
n = int(l[1])
for i in range(n-1):
  d1 = int(j[i+1]) - int(j[i])
  d2 = int(j[i+2]) - int(j[i+1])
  max = max(d1,d2)
  dt = k - int(max)
print(dt)


### FIXED CODE ###

KN = input().split(' ')
K = int(KN[0])
N = int(KN[1])
M = K/2
Al = input().split(' ')
A = []

for home in Al:
  A.append(int(home))

m = A[0]+(K-A[-1])
 
for i in range(N-1):
  m = max(m,abs(A[i]-A[i+1]))

print(K-m)
n, m = set(map(int, input().split()))
a = set(map(int, input().split()))
count = 0
for x in a:
    if x >= sum(a) / (4 * m):
        count += 1
if m <= count:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for x in a:
    if x >= sum(a) / (4 * m):
        count += 1
if m <= count:
    print("Yes")
else:
    print("No")
K = int(input())
X = int(input())
A=X-K+1
B=X+K-1
L=[]
for i in range(A,B):
  if i > 1000000 or i < -1000000:
    continue
  L.attend(i)
print(*L)

### FIXED CODE ###

K,X = map(int,input().split())
A=X-K+1
B=X+K-1
L=[]
for i in range(A,B+1):
  if i > 1000000 or i < -1000000:
    continue
  L.append(str(i))
print(*L)
i = int(input().replace(' ',''))
if i == i ** 0.5 * 2
    print("Yes")
else:
    print("No")


### FIXED CODE ###

i = int(input().replace(' ',''))
if i == int(i ** 0.5) ** 2:
    print("Yes")
else:
    print("No")
a=list(map(input().split()))
print(len(set(a)))

### FIXED CODE ###

a=input().split()
print(len(set(a)))
from collections import Counter
from functools import reduce 
n=int(input())
print(''.join(sorted(list(reduce(lambda a,b: Counter(a) & Counter(b), [sorted(input()) for i in range(n)]).elements()))))

### FIXED CODE ###

from collections import Counter
from functools import reduce 
n=int(input())
if n == 1: 
    print(''.join((sorted(input()))))
else:
    print(''.join(sorted(list(reduce(lambda a,b: Counter(a) & Counter(b), [sorted(input()) for i in range(n)]).elements()))))
n,k=map(int,input().split())
lists=list(map(int,input().split()))
a=format(k,"b")
length=max(len(a),len(format(max(lists),"b")))
fixedlists=[0]*n
uselists=[0]*length
for some in lists:
    check=format(some,"0%ib"%length)

    for i in range(length):
        if check[i]=="1":
            uselists[length-1-i]+=1         
if k>=1:
    order=0
    for i in range(length):
        if  2**i<=k<2**(i+1):
            order=i
            break  
            
    fixedlists=[0]*(k-2**order+1)
    for g in range(0,k-2**order+1):
        fixedlists[g]=format(g,"0%ib"%order)
        
    ans1=0
    ans2=0
    for j in range(order):
        ans1+=(2**j)*max(uselists[j],n-uselists[j])
        
    for j in range(order+1,length):
        ans2+=(2**j)*uselists[j]
    ans2+=(2**order)*(n-uselists[order])
    bigger=0
    for g in range(0,k-2**order+1):
        some=fixedlists[g]
        checker=0
        for i in range(order):
            if some[i]=="1":
                checker+=(2**(order-1-i))*(n-uselists[i])
            else:
                checker+=(2**(order-1-i))*uselists[i]
                
        bigger=max(bigger,checker)  
        
    ans2=ans2+bigger
    print(max(ans1,ans2))
    
elif k==0:
    ans=0
    for i in range(length):
        if uselists[i]=="1":
            ans+=(2**i)*(n-uselists[i])
        else:
            ans+=(2**i)*uselists[i]     
    print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)
def main():
    import sys
    input=sys.stdin.readline
    
    n,q=map(int,input().split())
    tree=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    cnt=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        cnt[p]+=x
    
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                cnt[e]+=cnt[i]
                dfs(e,i)
    dfs(0)   
    print(*cnt)

if __name__=='__main__':
    main()



### FIXED CODE ###

import sys
input=sys.stdin.readline

n,q=map(int,input().split())
tree=[[] for i in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  tree[a].append(b)
  tree[b].append(a)

ans=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

from collections import deque
q=deque([0])
while q:
  i=deque.popleft(q)
  for leaf in tree[i]:
    q.append(leaf)
    ans[leaf]+=ans[i]
    tree[leaf].remove(i)

print(*ans)
N = input()
Hlist = list(map(int, input().split()))
import numpy
a = numpy.argsort(Hlist)
count=0
while True:
    if a[-1]==0:
        count+=1
        break
    else:
        m = a.pop(-1)
        a = [i for i in a if a[-1] >= i]
        count+=1
print(count)

### FIXED CODE ###

N = int(input())
Hlist = list(map(int, input().split()))
count=0
maxHi=1
for i in range(N):
    if Hlist[0] >= maxHi:
        count+=1
        maxHi=Hlist.pop(0)
    else:
        del Hlist[0]
print(count)
import sys
n,m=map(int,input().split())
l=[0]*n
k=-1
for i in range(n):
    s,c=map(int,input().split())
    if s==1:
        if c==0:
            print(-1)
            sys.exit()
    if l[s-1]!=0:
        if l[s-1]==c:
            pass
        else:
            print(-1)
            sys.exit()
    l[s-1]=c
a=""
for j in range(n):
    a+=str(l[j])
if a[0]=="0":
    a[0]=="1"
print(int(a))

### FIXED CODE ###

import sys
n,m=map(int,input().split())
a1=0
a2=0
a3=0
c1=0
c2=0
c3=0
for i in range(m):
    s,c=map(int,input().split())
    if s==1:
        if c1==1:
            if a1==c:
                pass
            else:
                print(-1)
                sys.exit()
        else:
            a1=c
            c1=1
    if s==2:
        if c2==1:
            if a2==c:
                pass
            else:
                print(-1)
                sys.exit()
        else:
            a2=c
            c2=1
    if s==3:
        if c3==1:
            if a3==c:
                pass
            else:
                print(-1)
                sys.exit()
        else:
            a3=c
            c3=1
if n==1:
    pass
else:
    if c1==0:
        a1=1
if n==1:
    ans=a1
elif n==2:
    ans=a1*10+a2
else:
    ans=a1*100+a2*10+a3
k=ans//10**(n-1)
if k==0:
    if n==1:
        print(ans)
    else:
        print(-1)
else:
    print(ans)
while True:
    try:
        input_line = input()
        if input_line == '':
            break
        else:
            nums = list(map(int, input_line.split()))
            max_num = max(nums)
            nums.remove(max_num)
            if max_num**2 == nums[0]**2 + nums[1]**2:
                print("YES")
            else:
                print("NO")
    except EOFError:
        break


### FIXED CODE ###

n = int(input())
for i in range(0, n):
    nums = list(map(int, input().split()))
    max_num = max(nums)
    nums.remove(max_num)
    if max_num**2 == nums[0]**2 + nums[1]**2:
        print("YES")
    else:
        print("NO")
n,k = map(int,input().split())
mod = 10**9 + 7

fact = [1]
finv = [1]
for i in range(1, 2*n):
    fact.append((fact[i-1] * i) % mod)
    finv.append(pow(fact[i], mod-2, mod))

if n-1 <= k:
    print((fact[2*n-1] * finv[n] * finv[n-1]) % mod)

ans = 0
for i in range(k+1):
    ans += fact[n] * finv[n-i] * finv[i] * fact[n-1] * finv[n-1-i] * finv[i]
    ans %= mod

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
mod = 10**9 + 7

fact = [1]
finv = [1]
for i in range(1, 2*n):
    fact.append((fact[i-1] * i) % mod)
    finv.append(pow(fact[i], mod-2, mod))

if n-1 <= k:
    print((fact[2*n-1] * finv[n] * finv[n-1]) % mod)
    exit()

ans = 0
for i in range(k+1):
    ans += fact[n] * finv[n-i] * finv[i] * fact[n-1] * finv[n-1-i] * finv[i]
    ans %= mod

print(ans)
N = int(input())

for i in range(9,0,-1):
	if N%i==0:
      for j in range(9,0,-1):
      	if N%(i*j)==0:
          print("Yes")
        else:
          print("No")
  

### FIXED CODE ###

N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if i * j == N:
            break
    if i * j == N:
        print("Yes")
        break
    elif i == 9 and i * j != N:
        print("No")
def searchyen(n, y):
	for i in range(0, n+1):
		for j in range(0, n+1-i):
			if 10000*i + 5000*j + 1000*(n-i-j) == y:
				return [i, j, k]
	return [-1, -1, -1]

inpt = map(int, raw_input().split())

ans = searchyen(inpt[0], inpt[1])
print str(ans[0]) + ' ' + str(ans[1]) + ' ' + str(ans[2])


### FIXED CODE ###

def searchyen(n, y):
	for i in range(0, n+1):
		for j in range(0, n+1-i):
			if 10000*i + 5000*j + 1000*(n-i-j) == y:
				return [i, j, n-i-j]
	return [-1, -1, -1]

inpt = map(int, raw_input().split())

ans = searchyen(inpt[0], inpt[1])
print str(ans[0]) + ' ' + str(ans[1]) + ' ' + str(ans[2])
import sys
S,T = map(str,input().split())
for i in range(len(S)):
  tmp = S[-1]
  S[-1] = ""
  S.insert(0,tmp)
  if S == T:
    print("Yes")
    sys.exit()
print("No")
    

### FIXED CODE ###

import sys
S = input()
T = input()
for i in range(len(S)):
  tmp = S[-1]
  S = tmp + S[:-1]
  if S == T:
    print("Yes")
    sys.exit()
print("No")
N = int(input())
GACHA=set()
for n in range(N):
  GACHA.add(input())
print(len(GACHA))

### FIXED CODE ###

import itertools

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

ans=0
for A in itertools.combinations_with_replacement([m for m in range(1,M+1)], N):
  ans2=0
  for (a,b,c,d) in ABCD:
    if A[b-1]-A[a-1]==c:
      ans2+=d
  ans=max(ans, ans2)
print(ans)
A, B = map(int, input().split())
 
if A + B < 10: print(str(C))
else: print('error')

### FIXED CODE ###

A, B = map(int, input().split())
 
if A + B < 10: print(A+B)
else: print('error')
inp1 = input()
inp1 = int(inp1)
inp2 = input()
inp2 = list(inp2)

ans = 1
for i in inp2:
    if i != '1'
        ans = int(i)
        break

print(ans)

### FIXED CODE ###

inp1 = input()
inp1 = list(inp1)
inp2 = input()
inp2 = int(inp2)

ans = 1
count = 0
for i in inp1:
    if i != '1':
        ans = int(i)
        break
    else:
        count += 1

if count >= inp2:
    ans = 1

print(ans)
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最大重量 """
    V = 10**6
    dp_max = 0
    dp = [dp_max] * (V + 1)
    dp[0] = 0   # 境界条件：　価値0 の時は重さは0

    for item in range(N):
        if single:
            S = range(V, price_list[item]-1, -1)
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = max2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return min(price for price in range(V+1) if dp[price] >= W)


#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


W, N = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


print(knapsack_price(single=False))


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


### FIXED CODE ###

def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さを固定した時の最小価値 """
    weight_max = max(weight_list)
    price_max = max(price_list)
    W2 = W + weight_max
    dp_max = float("inf")  # 総和価値の最大値
    dp = [dp_max] * W2
    dp[0] = 0               # 重さ 0 の時は価値 0

    for item in range(N):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W2)
        for weight in S:
            dp[weight] = min2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return min(dp[w] for w in range(W, W2))

#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


W, N = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


print(knapsack_weight(single=False))


############################################################################################
x,n=map(int,input().split())

sett=list(map(int,input().split()))
arr=[i for i in range(-1,102) if i not in sett]

min_=100000
num=0
for i in arr:
	if abs(x-i)<min_:
		min_=abs(x-i)
		num=i



print(num)


### FIXED CODE ###

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

print(arr.index(0)+1)
import math
r = int(input())

print("%f %f" % (r*r*math.pi, 2*r*math.pi))


### FIXED CODE ###

import math
r = float(input())

print("%f %f" % (r*r*math.pi, 2*r*math.pi))
n, h, w = map(int, input().split())
print((n-h+1)*(n-w+1))

### FIXED CODE ###

n = int(input());h = int(input());w = int(input())
print((n-h+1)*(n-w+1))
K, N = input().split()
i, lists = 0, []
while i < N:
    lists.append(eval(input()))
    i += 1
if 0 in lists:
   lists.remove(0) 
print(max(lists) - min(lists))

### FIXED CODE ###

string = input("").lower()
print("Yes" if (string[2] == string[3]) and (string[4] == string[5]) else "No")
x,n = map(int,input().split())
if n == 0:
  print(x)
  exit()
if n != 0:
  p = sorted(map(int,input().split()))
aa = []
for i in range(1,101):
  if not i in p:
    aa.append(i)
bb = []
for A in aa:
  eee = abs(x-A)
  bb.append(eee)

ans = bb.index(min(bb))
print(aa[ans])



### FIXED CODE ###

x,n = map(int,input().split())
if n == 0:
  print(x)
  exit()
if n != 0:
  p = sorted(map(int,input().split()))
aa = []
for i in range(1,101):
  if not i in p:
    aa.append(i)
bb = []
if len(aa) == 0:
  if abs(x-(0)) <= abs(x-101):
    print(0)
    exit()
  else:
    print(101)
    exit()
else:
  for A in aa:
    eee = abs(x-A)
    bb.append(eee)

ans = bb.index(min(bb))
if abs(x-(0)) <= min(bb):
  print(0)
  exit()
elif abs(x-101) < min(bb):
  print(101)
  exit()
else:
  print(aa[ans])
  exit()
a,b,c=map(int,input().split())

answer = b//a

if answer<c:
  print(answer)
  else:
    print(c)

### FIXED CODE ###

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

if b//a <= c:
  print(b//a)
  
else:
  print(c)
inp = input().split()

input().split() == "2 5 7" == ["2", "5","7"]

A = int(inp[0])
B = int(inp[1])
C = int(inp[2])

if A + B + C >= 22:
	print("bust")
else:
	print("win")

### FIXED CODE ###

a1, a2, a3 = map(int, input().split())
if 1 <= a1 <= 13 and 1 <= a2 <= 13 and 1 <= a3 <= 13:
    if a1 + a2 + a3 >= 22:
        print('bust')
    else:
        print('win')
def solve_dp(p):
    while p < N:
        if p < N - 1:
            if dp[p+1] > (abs(h[p] - h[p+1]) + dp[p]):
                dp[p+1] = abs(h[p] - h[p+1]) + dp[p]

        if p < N - 2:
            if dp[p+2] > (abs(h[p] - h[p+2]) + dp[p]):
                dp[p+2] = abs(h[p] - h[p+2]) + dp[p]

        print(dp)
        p += 1

N = int(input())
h = [int(x) for x in input().split()]
dp = [100000000] * (N + 1)
dp[0] = 0
solve_dp(0)
print(dp[N-1])


### FIXED CODE ###

def solve_dp(p):
    i = 0
    while i < N:
        if p == 0:
            dp[0] = 0
        elif p == 1:
            dp[1] = abs(h[1] - h[0])
        elif p >= 2 and p <= N - 1:
            if abs(h[p] - h[p-1]) + dp[p-1] > abs(h[p] - h[p-2]) + dp[p-2]:
                dp[p] = abs(h[p] - h[p-2]) + dp[p-2]
            else:
                dp[p] = abs(h[p] - h[p-1]) + dp[p-1]
        else:
            return

        p += 1
        i += 1

N = int(input())
h = [int(x) for x in input().split()]

dp = [0] * N
solve_dp(0)

print(dp[N-1])
# たぶん最小の値は最小公倍数になりそう

n, m = map(int, input().split())
s, t = input(), input()


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


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


l = lcm(n, m)
arr = [0] * l

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if arr[x] != 0 and arr[x] != t[i]:
        print(-1)
        exit()
print(l)

### FIXED CODE ###

# たぶん最小の値は最小公倍数になりそう
# 内包表記 -> TLE
# [0]*l -> RE

n, m = map(int, input().split())
s, t = input(), input()


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


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


l = lcm(n, m)
arr = {}

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if x in arr and arr[x] != t[i]:
        print(-1)
        exit()
print(l)