Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
while True:
    flag = False
    for i in range(N):
        if not flag and A[i] % 2 == 0:
            A[i] = A[i] // 2
            flag = True
        else:
            A[i] *= 3
    if flag:
        ans += 1
    else:
        break
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    while True:
        if A[i] % 2 == 0:
            ans += 1
            A[i] = A[i] // 2
        else:
            break
print(ans)
### BUGGY CODE ###

N=int(input())
s=[2,3,5]
ans=[]
for i in range(7,55555):
    for j in s:
       if i%j==0:
           break
       if i%j!=0:
           s.append(i)
           
       if i%3==1:
           ans.append(i)
           
    if len(ans)==N:
        break
    
for i in range(N):
    print(ans[i],end=",")

### FIXED CODE ###


N=int(input())
s=[2,3,5]
ans=[]
for i in range(7,55555):
    for j in s:
       if i%j==0:
           break
       if j>i**(0.5):
           
           s.append(i)
           
           if i%5==1:
               ans.append(i)
           break
           
    if len(ans)==N:
        break
    
for i in range(N):
    print(ans[i],end=" ")
### BUGGY CODE ###

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

c=[]

for x in range(n+1):

    c.append(int(a*x/b)-a*int((x/b)))

print(max(c))


### FIXED CODE ###

a,b,n=map(int,input().split())
#0<=x<=b-1でfloor(x/b)は0となるので単調増加になる
#単調増加なのでb-1とnの小さいほうがxの最大値
x=min(b-1,n)

print(a*x//b)
### BUGGY CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)

ex =0
ext = []
ext2 = []
for f in range(n):
    xs = list(range(1,int(p[f])+1))
    xs = sum(xs)*1/int(p[f])
    ext.append(xs)

ext2.append(ext[0])
for i in range(1,n):
    ext2.append(ext2[i-1]+ext[i])

ex = ext2[k-1]
for j in range(1,n-k+1):
    ext3 =ext2[j+k-1]-ext2[j-1]
    if ext3 > ex: ex = ext3

print('{:.12f}'.format(ex))

### FIXED CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
#p = [int(s) for s in p]

#print(p)

ex =0
ext = []
ext2 = []
for f in range(n):
    pi = int(p[f])
    xs =(pi+1)/2
    ext.append(xs)

ext2.append(ext[0])
for i in range(1,n):
    ext2.append(ext2[i-1]+ext[i])

ex = ext2[k-1]
for j in range(1,n-k+1):
    ext3 =ext2[j+k-1]-ext2[j-1]
    if ext3 > ex: ex = ext3

print('{:.12f}'.format(ex))
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(input())

# setに変換
setS = set(s)

maxList = []
maxCount = 0
for word in setS:
    # 文字列の出現回数を数える
    cnt = s.count(word)
    if cnt > maxCount:
        maxCount = cnt
        # 初期化
        maxList = []
        maxList.append(word)
    elif cnt == maxCount:
        maxList.append(word)

maxList.sort()

for word in maxList:
    print(word)

    

### FIXED CODE ###

from collections import Counter

N = int(input())
s = []
for i in range(N):
    s.append(input())

sc = Counter(s)
maxNum = sc.most_common()[0][1]
keys = [k for k , v in sc.most_common() if v == maxNum]
keys.sort()
for word in keys:
    print(word)
### BUGGY CODE ###

import heapq


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))+[-100]*10
B = list(map(int, input().split()))+[-100]*10
C = list(map(int, input().split()))+[-100]*10
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Done = [[[False] * Z for _ in range(Y)] for __ in range(X)]
Q = []
Done[0][0][0] = True
heapq.heappush(Q, (-(A[0] + B[0] + C[0]), 0, 0, 0))
cnt = K
while cnt > 0:
    cnt -= 1
    ans, a, b, c = heapq.heappop(Q)
    print(-ans)
    if (a + 1 < X) and not(Done[a+1][b][c]):
        heapq.heappush(Q, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
        Done[a+1][b][c] = True
    if (b + 1 < Y) and not (Done[a][b+1][c]):
        heapq.heappush(Q, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
        Done[a][b+1][c] = True
    if (c + 1 < Z) and not(Done[a][b][c+1]):
        heapq.heappush(Q, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
        Done[a][b][c+1] = True


### FIXED CODE ###

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()))

D = []
for a in A:
    for b in B:
        D.append(a + b)
D.sort(reverse=True)
if len(D) > K:
    D = D[:K]
E = []
for d in D:
    for c in C:
        E.append(c + d)

E.sort(reverse=True)
for i, e in enumerate(E):
    if i >= K:
        break
    print(e)
### BUGGY CODE ###

S = input()
Q = int(input())

reverse = False

for i in range(Q):
    query = input().split()
    if query[0] == '1':
        reverse = not reverse
    if query[0] == '2':
        if query[1] == '1':
            if not reverse:
                S = query[2] + S
            else:
                S = S + query[2]
        if query[1] == '2':
            if not reverse:
                S = S + query[2]
            else:
                S = query[2] + S

if not reverse:
    print(S)
else:
    for i in range(1, len(S)+1):
        print(S[-i], end='')


### FIXED CODE ###

S = input()
Q = int(input())

front = ''
back = S
reverse = False

for i in range(Q):
    query = input().split()
    if query[0] == '1':
        reverse = not reverse
    if query[0] == '2':
        if query[1] == '1':
            if not reverse:
                front = front + query[2]
            else:
                back = back + query[2]
        if query[1] == '2':
            if not reverse:
                back = back + query[2]
            else:
                front = front + query[2]

if not reverse:
    print(front[::-1] + back)
else:
    print(back[::-1] + front)
### BUGGY CODE ###

import heapq
from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

def dijkstra(start):
    c_l = [float('inf') for i in range(N)]
    c_l[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)  # pop
        if c_l[src] < prov_cost:
            continue
        for d in range(N):
            cost = g[src][d]
            if cost != float('inf') and c_l[d] > c_l[src] + cost:
                c_l[d] = c_l[src] + cost
                heapq.heappush(q, (c_l[d], d))
    else:
        return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)


### FIXED CODE ###

from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c


def dijkstra(start):
    c_l = [float('inf')] * N
    c_l[start] = 0
    visited = [False] * N
    while True:
        min_v = float('inf')
        next = -1
        visited[start] = True
        for i in range(N):
            if visited[i]:
                continue
            if g[start][i]:
                d = c_l[start] + g[start][i]
                if d < c_l[i]:
                    c_l[i] = d
                if min_v > c_l[i]:
                    min_v = c_l[i]
                    next = i
        start = next
        if next == -1:
            break
    return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)
### BUGGY CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            while (dp[i][length] > mod):
                dp[i][length] -= mod
            #dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            while (dp2[i][length] > mod):
                dp2[i][length] -= mod
            #dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][T-1]+B[i])

        for j in range(0,T):

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][T-1]+B[i])

        for j in range(0,T):

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
m=list(input())
ans=10**5
for i in range(n):
    p=0
    x=m[:i]
    y=m[i+1:]
    p=x.count("W")+y.count("E")
    ans=min(ans,p) 
print(ans)



### FIXED CODE ###

n=int(input())
m=list(input())
p=m.count("E")
s=p
for i in m:
    if i=="E":
        p-=1
    else:
        p+=1
    s=min(s,p)
print(s)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()

        if maze[h][w]:
            continue

        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in que and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))

        for dh,dw in [
            [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
            [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
            [0,-2], [0, 2], 
            [1,-2], [1,-1], [1, 1], [1, 2], 
            [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
        ]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in nque and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))

        maze[h][w] = 1
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

### FIXED CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([(*c, 0)])
passed = set()
while que:
    h,w,dist = que.popleft()
#         print(f'{h=},{w=}')
    if (h,w) == d:
        print(dist)
        exit()
    if (h,w) in passed:
        continue
    passed.add((h,w))
    for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
            que.appendleft((nh, nw, dist))

    for dh,dw in [
        [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
        [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
        [0,-2], [0, 2], 
        [1,-2], [1,-1], [1, 1], [1, 2], 
        [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
    ]: 
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
            que.append((nh, nw, dist + 1))
print(-1)
### BUGGY CODE ###

N,K = map(int,input().split())
A=  list(map(int,input().split()))
now = 0
if K <= N:
    for i in range(K):
        now = A[now]-1
    print(now+1)
else:
    alr = [0]
    now = 0
    for i in range(K):
        now = A[now]-1
        if now not in alr:
            alr.append(now)
        else:
            loop = alr[alr.index(now):]
            rem = K - i - 1
            break
    ans = loop[rem%len(loop)]+1
    print(ans)
    

### FIXED CODE ###

N,K = map(int,input().split())
A=  list(map(int,input().split()))
now = 0
if K <= N:
    for i in range(K):
        now = A[now]-1
    print(now+1)
else:
    alr = [0]
    alr2 = [False for i in range(N)]
    alr2[0] = True
    now = 0
    for i in range(K):
        now = A[now]-1
        if alr2[now] == False:
            alr.append(now)
            alr2[now] = True
        else:
            loop = alr[alr.index(now):]
            rem = K - i - 1
            break
    ans = loop[rem%len(loop)]+1
    print(ans)
### BUGGY CODE ###

import numpy as np
N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[0:L,R-1:] += 1
for i in range(Q):
    p,q = map(int,input().split())
    print(int(lis[p-1,q-1]))




### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[L-1,R-1] += 1
#二次元累積和
for i in range(N-2,-1,-1):
    lis[i] += lis[i+1]
for j in range(1,N):
    lis[:,j] += lis[:,j-1]

for _ in range(Q):
    p,q = map(int,input().split())
    print(int(lis[p-1,q-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] != 0:
      CU.add(CE[(min(u,v),max(u,v))])
  CC = set()
  for cc in range(1,maxc+1):
    if cc not in CU:
      CC.add(cc)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = c+1
  if cc > maxc:
    cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,cc)
      cc += 1
      if cc > maxc:
        cc = 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1):
            for a in range(n+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p == n-1:
            break
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
a,b,n = map(int,input().split())
d = 0
i = 0
for i in range(1,n+1):
    c = int(a*i/b)-a*int(i/b)
    if c >= d:
        d = c
    else:
        i += 1
        if i > 1:
            print(int(a*(i-2)/b)-a*int((i-2)/b))
            sys.exit()
print(d)

### FIXED CODE ###

a,b,n = map(int,input().split())
if n>= b-1:
    print(int(a*(b-1)/b)-a*int((b-1)/b))
else:
    print(int(a*n/b)-a*int(n/b))
### BUGGY CODE ###

n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
b = a[:]
ans = 0
for k in range(n):
    for i in range(n):
        b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print ans


### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))