Harryxun/stf_run huggingface dataset:
import itertools


def main():
    n, m, x = input_list()

    costs = []
    contents = [[] for i in range(m)]
    contents_with_index = [[] for i in range(m)]
    for i in range(n):
        b = input_list()
        costs.append(b[0])
        for index, c in enumerate(b[1:]):
            contents[index].append(c)
            contents_with_index[index].append((str(i), c))

    for c in contents:
        if sum(c) < x:
            print(-1)
            exit()

    results = [[] for i in range(m)]
    for index, c in enumerate(contents_with_index):
        for i in range(1, m+1):
            for cv in itertools.combinations(c, i):
                s = sum([num[1] for num in cv])
                if s >= x:
                    results[index].append(','.join([num[0] for num in cv]))

    ans = set(results[0])
    for r in results:
        ans &= set(r)

    usable_cost = []
    for a in ans:
        usable_cost.append(sum(list(map(lambda x: costs[int(x)], a.split(',')))))

    print(min(usable_cost))


def input_list():
    return list(map(int, input().split()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, m, x = input_list()
    books = {}
    contents = {}
    for i in range(n):
        c = input_list()
        books[i] = c[0]
        contents[i] = c[1:m+1]

    if n == 1:
        if sum(contents[0]) >= x:
            print(books[0])
        else:
            print(-1)
        exit()

    ans = []
    for v in itertools.product([0, 1], repeat=n):
        understands = [0] * m
        ok = [False] * m
        a = 0
        for i, vi in enumerate(v):
            if vi == 0:
                continue
            for index, val in enumerate(contents[i]):
                understands[index] += val
                if understands[index] >= x:
                    ok[index] = True
            a += books[i]
        if all(ok):
            ans.append(a)

    if len(ans) > 0:
        print(min(ans))
    else:
        print(-1)
        # a = 0
        # for vi in v:
        #     for index, val in enumerate(contents[vi]):
        #         understands[index] += val
        #         if understands[index] >= x:
        #             ok[index] = True
        #     a += books[vi]
        # if all(ok):
        #     ans.append(a)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()
import sys
sys.setrecursionlimit(10000)

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

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        return find_head(tree[i])
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        tree[i] = find_head(tree[i])
        return tree[i]
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)
n = int(input())
 
for i in range((n//4)+1):
    for j in range((n//7)+1):
        if (i*4) + (j*7) == n:
            print("Yes")
            exit()
print("No"

### FIXED CODE ###

n = int(input())

fo = n // 4
se = n // 7

for i in range(fo+1):
    for j in range(se+1):
        if ((i*4) + (j*7)) == n:
            print("Yes")
            exit()
print("No")
#標準入力
X = int(input())

max_beki = 1
for i in range(1,X):
  for j in range(2,X):
    beki = i %% j
    
    if beki > max_beki:
      if beki <= X:
        max_beki = beki
      
print(max_beki)


### FIXED CODE ###

#標準入力
X = int(input())

max_beki = 1
for i in range(1,X):
  for j in range(2,X):
    beki = i ** j
    
    if beki > X:
      break
      
    elif beki > max_beki:
      max_beki = beki
 
print(max_beki)
lines = [[0,1,2], [3,4,5], [6,7,8],[0,3,6],[1,4,7],[2,4,8],[0,4,8],[2,4,6]]

table = [int(s) for s in input().split()]
table += [int(s) for s in input().split()]
table += [int(s) for s in input().split()]

lis = [int(input()) for _ in range(int(input()))]

ans = [ n in lis for n in table ]

for line in lines:
  valid = True
  for num in line:
    if not ans[num] :
      valid = False
      break

      if valid:
        print('Yes')
        return

      print('No')

### FIXED CODE ###

import sys
import math
from io import StringIO
import unittest

lines = [[0,1,2], [3,4,5], [6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]

def resolve():
    table = [int(s) for s in input().split()]
    table += [int(s) for s in input().split()]
    table += [int(s) for s in input().split()]

    lis = [int(input()) for _ in range(int(input()))]

    ans = [ n in lis for n in table ]

    for line in lines:
        valid = True
        for num in line:
            if not ans[num] :
                valid = False
                break

        if valid:
            print('Yes')
            return

    print('No')
resolve()
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if v != p:
      dfs(v, u)

n, m = map(int, input().split())
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1 if c else 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if not vis[v]:
      dfs(v, u)

n, m = map(int, input().split())
assert 2 <= n <= int(1e5)
assert 1 <= m <= int(1e5)
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  assert 1 <= u <= int(1e5)
  assert 1 <= v <= int(1e5)
  assert u < v
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 1)
num = int(input())
line = list(map(int,input().split()))
count = True
count_num = 0
while count:
    for i in range(num):
        if line[i] % 2 != 0:
            count = False
    if count:
        for i in range(num):
            line[i] /= 2
     count_num += 1     
print(count_num)

### FIXED CODE ###

num = int(input())
line = list(map(int,input().split()))
count = True
count_num = 0
while count:
    for i in range(num):
        if line[i] % 2 != 0:
            count = False
    if count:
        for i in range(num):
            line[i] /= 2
    count_num += 1
print(count_num-1)
n, m = map(int, input().split())
for i in range(1, min(m//n, int(m**0.5))+1)[::-1]:
    if m%i == 0:
        print(max(m//i, i)
        break

### FIXED CODE ###

n, m = map(int, input().split())
r = 1
for i in range(1, int(m**0.5)+1)[::-1]:
    if i<=m//n and m%i==0:
        if m//i<=m//n:
            r = max(r, m//i)
        else:
            r = max(r, i)
print(r)
a,b=map(int,input().split())
if a>b:
  print('a > b')
elif a<b:
  print('a < b')
else:
  print('a == b')

### FIXED CODE ###

a,b=map(int,input().split())
if a>b:
  print('a > b')
elif a<b:
  print('a < b')
else:
  print('a == b')
N,M = map(int,input().split())

memo = [0]*N

for i in range(M):
    s,c = map(int,input().split())
    if memo[s-1]==0:
        memo[s-1]=c
    else:
        if not memo[s-1]==c:
            print(-1)
            break

else:
    if memo[0]==0:
        memo[0]=1
    
    counter = 0
    for iterration,k in enumerate(memo):
        counter += k*(10**(len(memo)-iterration-1))
    print(counter)

### FIXED CODE ###

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


li = ["#"]*N
A = "#"
if N==1:
    for i in range(M):
        s,c = map(int,input().split())
        if not c==A and not A=="#":
            print(-1)
            exit()
        else:
            A=c
  
    if A == "#":
        print(0)
    else:
        print(int(A))
    exit()
    

for i in range(M):
    s,c = map(int,input().split())
    if s==1 and c==0:
        print(-1)
        break

    if not li[s-1]=="#" and not li[s-1]==c:
        print(-1)
        break
    if li[s-1]=="#":
        li[s-1]=c
    
else:
    if li[0]=="#":
        li[0]=1
        
    num="".join(map(str,li))
    num_new=num.replace("#","0")
    print(num_new)
a= int(input())
b= int(input())
c= int(input())
k= int(input())
ans= 0
 
for i in range(k):
  if a < b*(2**i) < c*(2**(k-i)):
    ans+=1
  else:
    ans+=0
  
print(Yes if ans>=1 else No)

### FIXED CODE ###

a, b, c = map(int, input().split())
k = int(input())
ans= 0
 
for i in range(k):
  if a < b*(2**i) < c*(2**(k-i)):
    ans+=1
  else:
    ans+=0
  
if ans>=1:
  print("Yes")
else:
  print("No")
list_A= [1,2,3]
a = input()
b = input()
list_A.remove(a)
list_A.remove(b)
print(list_A)

### FIXED CODE ###

list_A= [1,2,3]
a = int(input())
b = int(input())
list_A.remove(a)
list_A.remove(b)
print(list_A[0])
#!/usr/bin/env python3

import sys


def main(input):
    return input if len(input) == 2 else ''.join(reversed(input))

if __name__ == "__main__":
    print main(sys.stdin.readline().strip())


### FIXED CODE ###

#!/usr/bin/env python3

import sys


def main(input):
    return input if len(input) == 2 else input[::-1]

if __name__ == "__main__":
    print(main(sys.stdin.readline().strip()))
N,K=map(int,input().split())
List = list(map(int, input().split()))

for i in range(K):
  Flag = False
  data = [0]*N
  for j in range(N):
    if i-List[i] < 0:
      i-List[i] = 0
    data[i-List[i]] += 1
    if i+List[i]+1 < N:
      data[i+List[i]+1] +=-1
  List[0] = data[0]
  for j in range(N-1):
    List[i+1] = List[i] + data[i+1]
  if List.count(N) == N:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
A = input()
B = input()
result = int(A)*int(B)
if 9 < int(A):
    print(-1)
elif 9 < int(B):
    print(-1)

else:
    print(result)

### FIXED CODE ###

list = input().split(' ')
A = int(list[0])
B = int(list[1])
if A <= 9 and B <= 9:
    print(A*B)
else:
    print(-1)
from collections import Counter

n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

cnt = Counter(prime_factorize(n))
two_five = min(cnt[2],cnt[5])
x = 0
for key in cnt:
    if x < key:
        x = key
keta = len(str(key))

print(max(keta,-(-two_five//2)+1))

### FIXED CODE ###

n = int(input())
a = []
for i in range(1,int(n**(0.5))+1):
    if n%i == 0:
        a.append(i)
m = max(a)
c = int(n/m)
keta = len(str(c))
print(keta)
N=int(input())
A=list(map(int,input().split()))
A.sort()

F=[0]*(10**6+11)

for a in A:
    if F[a]==2:
        F[a]=1
        continue
    elif F[a]==0:
        F[a]=2
    k=2*a
    while 1:
        F[k]=1
        k+=a
        if not k<=10**6+10:
            break
res=0
for a in A:
    if F[a]==2:res+=1
print(res)

### FIXED CODE ###

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

F=[0]*(10**6+11)
# 0:OK/未調査 1:NG 2:調査した頂点 3:二度調査した頂点

for a in A:
    if F[a]==1:
        continue
    if F[a]==2:
        F[a]=1
        continue
    elif F[a]==0:
        F[a]=2
    k=2*a
    while k<=10**6+1:
        F[k]=1
        k+=a
            
res=0
for a in A:
    if F[a]==2:
        res+=1
print(res)
# -*- coding: utf-8 -*-

def move(S, before_a, before_b, a_index, b_index, g_a, g_b):
    if len(S)<=a_index or len(S) <= b_index:
        return -1
    if S[a_index]=='#' or S[a_index]=='B':
        return 0
    elif S[b_index]=='#' or S[b_index]=='A':
        return 0
    if a_index==g_a and b_index==g_b:
        return 100
    S[before_a] = '.'
    S[before_b] = '.'

    S[a_index] = 'A'
    S[b_index] = 'B'
    rr1 = 0
    rr2 = 0
    rr3 = 0
    rr4 = 0
    rr1 = move(S, a_index, b_index, a_index+1, b_index, g_a, g_b)
    rr2 = move(S, a_index, b_index, a_index+2, b_index, g_a, g_b)
    rr3 = move(S, a_index, b_index, a_index, b_index+1, g_a, g_b)
    rr4 = move(S, a_index, b_index, a_index, b_index+2, g_a, g_b)
    return max([rr1,rr2,rr3,rr4])
#    return 1

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

S = list(input())

S[A-1] = 'A'
S[B-1] = 'B'

a_index = A-1
b_index = B-1

r1 = 0
r2 = 0
r3 = 0
r4 = 0

if len(S)>a_index:
    r1 = move(S, a_index, b_index, a_index+1, b_index, C-1, D-1)
    if r1==100:
        print('Yes')
        exit()
if len(S)-1>a_index:
    r2 = move(S, a_index, b_index, a_index+2, b_index, C-1, D-1)
    if r2==100:
        print('Yes')
        exit()
if len(S)>b_index:
    r3 = move(S, a_index, b_index, a_index, b_index+1, C-1, D-1)
    if r3==100:
        print('Yes')
        exit()
if len(S)-1>b_index:
    r4 = move(S, a_index, b_index, a_index, b_index+2, C-1, D-1)
    if r4==100:
        print('Yes')
        exit()


print('No')


### FIXED CODE ###

#!/usr/bin/env python3

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

#hunuke

h = S[A-1:D+1].count('##')
m3 = S[B-2:D+1].count('...')

if C < D:
    if h == 0: print('Yes')
    else: print('No')
else:
    if m3 != 0 and h == 0:
        print('Yes')
    else: print('No')
N = int(input())

def factorial(num):
    if num == 1:
        return 1
    return num * factorial(num - 1)

def count_order(group):
    numbers = [i for i in range(1, N + 1)]
    res = 1
    for i in range(len(group) - 1):
        num = group[i]
        res += numbers.index(num) * pattern[-(i + 1)]
        numbers.pop(numbers.index(num))
    return res


P = list(map(int, input().split()))
Q = list(map(int, input().split()))

pattern = [factorial(i) for i in range(1, N)]
res_p = count_order(P)
res_q = count_order(Q)

print(abs(res_p - res_q))


### FIXED CODE ###

N = int(input())

def factorial(num):
    if num == 1:
        return 1
    return num * factorial(num - 1)

def count_order(group):
    numbers = [i for i in range(1, N + 1)]
    res = 1
    for i in range(len(group) - 1):
        num = group[i]
        res += numbers.index(num) * pattern[-(i + 1)]
        numbers.pop(numbers.index(num))
    return res


P = list(map(int, input().split()))
Q = list(map(int, input().split()))

pattern = [factorial(i) for i in range(1, N)]
res_p = count_order(P)
res_q = count_order(Q)

print(abs(res_p - res_q))
n = int(input())
m = 0
p = list(range(2, n + 1)) + [1]
for i, pi in enumerate(p):
  m += (i + 1) % pi
print(m)

### FIXED CODE ###

n = int(input())
print(n * (n - 1) // 2)
n = int(input())
a = [int(i) for i in input().split()]

if n < 20:
    d = a.copy()

    for i in range(1, n // 2):
        b = [0] * n
        c = -10 ** 24
        ans = -10 ** 24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]
            ans = max(ans, c + d[j])

        a = b.copy()
    print(ans)
    exit()

b = a[:10]
e = [True]*10

for i in range(1, n // 2):
    c = [0] * 10
    f = [False]*10
    d = -10**24
    for j in range(10):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(10):
    if e[i]:
        ans = max(ans, b[i])
print(ans)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

if n // 2 == 1:
    print(max(a))
    exit()
if n < 20:
    d = a.copy()
    
    for i in range(1, n // 2):
        b = [0] * n
        c = -10 ** 24
        ans = -10 ** 24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]
            ans = max(ans, c + d[j])

        a = b.copy()
    print(ans)
    exit()

b = a[:10]
e = [True]*10

for i in range(1, n // 2):
    c = [0] * 10
    f = [False]*10
    d = -10**24
    for j in range(10):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(10):
    if e[i]:
        ans = max(ans, b[i])
print(ans)
N = int(input())
a = [sorted(list(input())) for i in range(N)]
b = set(a)
print(len(a) - len(b))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
c=list(map(int, input().split()))

W = c[0]
H = c[1]
x = c[2]
y = c[3]



if W*y < W*H / 2:
    S1 = W*y
elif W*y == W*H / 2:
    S1 = int(W*y)
else:
    S1 = W*H - W*y

if H*x < W*H / 2:
    S2 = H*x
elif H*x == W*H / 2:
    S2 = int(H*x)
else:
    S2 = W*H - H*x

if S1 < S2:
    Sm = S2
    co = 0
elif S1 > S2:
    Sm = S1
    co = 0
else:
    Sm = S1
    co = 1
    
print(Sm,co)

### FIXED CODE ###

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

if x < a:
    print(0)
else:
    print(10)
n=map(str,raw_imput().split())
n.sort()
n.reverse()
print(' '.join(n))

### FIXED CODE ###

n=map(int,raw_input().split())
n.sort()
n.reverse()
n=map(str,n)
print(" ".join(n))
import sys
sys.setrecursionlimit(10000)

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(2)
for i in anslist:
    print(i%2)
import sys
input=sys.stdin.read
*x,=map(int, input().split("\n"))
tmp=100
for i in range(5):
    if x[i]%10:
        tmp = min(tmp,x[i]%10)
        x[i]//=10
        x[i]*= 10
        x[i]+=10
ans= sum(x)
if tmp<100:
    ans-=10
    ans+=tmp
print(ans)
    


### FIXED CODE ###

#import sys
#input=sys.stdin.read
#*x,=map(int, input().split("\n"))
x=[int(input()) for _ in range(5)]
tmp=100
for i in range(5):
    if x[i]%10:
        tmp = min(tmp,x[i]%10)
        x[i]//=10
        x[i]*= 10
        x[i]+=10
ans= sum(x)
if tmp<100:
    ans-=10
    ans+=tmp
print(ans)
a,b =map(input().split())
if a<10:a=10-a
else:a=0
print(b+ (a*100))

### FIXED CODE ###

a,b =map(int, input().split())
if a<10:a=10-a
else:a=0
print(b+ (a*100))
import copy
n = int(input())
a = [int(input()) for _ in range(n)]
b = (copy.copy(a)).sort(reverse=True)
m = max(a)

for i in range(n):
    if a[i] != max(a):
        print(max(a))
    else:
        print(b[1])

### FIXED CODE ###

import copy
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = copy.copy(a)
a.sort(reverse=True)
for i in range(n):
    if b[i] == a[0]:
        print(a[1])
    else:
        print(a[0])
def a(s):
    count = 0
    for i in range(len(s) - 2):
        if s[i] == s[i + 1]:
            s = s[:i + 1] + 'A' + s[i + 2:]
            count += 1
    if s[-1] == s[-2]:
        count += 1
    return count


s = input()
k = int(input())
if s[0] != s[-1] or k == 1:
    print(a(s) * k)
elif k == 2:
    new_s = s * 2
    print(a(new_s))
elif len(s) == s.count(s[0]):
    new_s = s * 2
    count_2 = a(new_s)
    print(count_2 * (k // 2) + a(s) * (k % 2))
else:
    new_s = s * 2
    count_2 = a(new_s)
    count_3 = a(new_s + s)
    diff = count_3 - count_2
    print(count_3 + (k-3) * diff)


### FIXED CODE ###

def a(s):
    count = 0
    test = s[0]
    for i in range(len(s) - 1):
        if s[i] == s[i + 1] and test[i] != 'A':
            # s = s[:i + 1] + 'A' + s[i + 2:]
            test += 'A'
            count += 1
        else:
            test += s[i]
    return count


s = input()
k = int(input())
if s[0] != s[-1] or k == 1:
    print(a(s) * k)
elif k == 2:
    new_s = s * 2
    print(a(new_s))
elif len(s) == s.count(s[0]):
    new_s = s * 2
    count_2 = a(new_s)
    print(count_2 * (k // 2) + a(s) * (k % 2))
else:
    new_s = s * 2
    count_2 = a(new_s)
    count_3 = a(new_s + s)
    diff = count_3 - count_2
    print(count_3 + (k-3) * diff)
import sys
input= sys.sdtin.readline

N,M = map(int,input().split())
g=M//N#最大公約数になる可能性のある最大値
for i in range(g):
  if M%(g-i)==0:
    print(g-i)
    exit()

### FIXED CODE ###

import sys
input= sys.stdin.readline

N,M = map(int,input().split())
g=M//N#最大公約数になる可能性のある最大値
for i in range(g):
  if M%(g-i)==0:
    print(g-i)
    exit()
  if M%(N+i)==0:
    print(M//(N+i))
    exit()
s=str(input())
print(s.count(1))


### FIXED CODE ###

s=str(input())
print(s.count("1"))
import collections
N = int(input())
A = input().split()
A.insert(0,0)
x = [0]*N
for j in range(N):
    print(c[str(j+1)])


### FIXED CODE ###

N = int(input())
A = input().split()
x = [0]*N
for i in range(N-1):
    x[int(A[i])-1]+=1
for j in range(N):
    print(x[j])
import math
n, m = input().split()
m = int(m)
n = int(n)
if n == 1 or 0:
	nNum = 0
else:
	nNum = math.factorial(n) / (math.factorial(n-2) * math.factorial(2))
if m == 1 or 0:
	mNum = 0
else:
	mNum = math.factorial(m) / (math.factorial(m-2) * math.factorial(2))
print(int(mNum + nNum))

### FIXED CODE ###

import math
n, m = input().split()
m = int(m)
n = int(n)
if n == 1 or n == 0:
	nNum = 0
else:
	nNum = math.factorial(n) / (math.factorial(n-2) * math.factorial(2))
if m == 1 or m == 0:
	mNum = 0
else:
	mNum = math.factorial(m) / (math.factorial(m-2) * math.factorial(2))
print(int(mNum + nNum))
a = map(int,input().split())
for i in range(0,4):
    if a[i]==0:
        print(i+1)

### FIXED CODE ###

a = list(map(int,input().split()))
for i in range(0,5):
    if a[i]==0:
        print(i+1)