Harryxun/stf_run huggingface dataset:
n,m,d=map(int,input().split())

DP=[[[0]*m for _ in range(n)] for _ in range(m)]

for i in range(n):
    DP[0][i][0]=1

for i in range(1,m):
    for j in range(n):
        for k in range(m):
            if k==0:
                if j-d<0:
                    DP[i][j][k]=DP[i-1][j+d][0]
                elif j+d>=n:
                    DP[i][j][k]=DP[i-1][j-d][0]
                else:
                    DP[i][j][k]=DP[i-1][j+d][0]+DP[i-1][j+d][0]
            else:
                if j-d<0:
                    DP[i][j][k]=DP[i-1][j+d][k-1]+DP[i-1][j][k]
                elif j+d>=n:
                    DP[i][j][k]=DP[i-1][j-d][k-1]+DP[i-1][j][k]
                else:
                    DP[i][j][k]=DP[i-1][j+d][k-1]+DP[i-1][j-d][k-1]+DP[i-1][j][k]
            DP[i][j][k]=DP[i][j][k]/n

ans=0
for i in range(n):
    for j in range(1,m):
        ans+=DP[m-1][i][j]*j
ans=ans/n
print(ans)



### FIXED CODE ###

n,m,d=map(int,input().split())

if d==0:
    ans=(m-1)/n
else:
    ans=(n-d)*2*(m-1)/(n*n)

print(ans)
N,K = map(int, input(),split())

counter = 1
tmp = 1
while true:
    tmp *= K
    if tmp > N
        break
    counter += 1
print(counter)

### FIXED CODE ###

N,K = map(int, input().split())
 
counter = 1
tmp = 1
while True:
    tmp *= K
    if tmp > N:
        break
    counter += 1
print(counter)
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''
n,x = map(int, input().split())
al = list(map(int, input().split()))

st = SegTree(al, min, 10**18)
ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = i*x
    for j in range(n): # ind
        l = j-i
        if l >= 0:
            amin = st.query(l,j+1)
        else:
            amin1 = st.query(0,j+1)
            amin2 = st.query(l+n,n+1)
            amin = min(amin1,amin2)
        curr_i_ans += amin
    ans = min(ans, curr_i_ans) 
print(ans)

### FIXED CODE ###

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

costs = al[:]
curr_sums = sum(costs)

# curr_mins = al[:]
curr_mins = al[:]

ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = 0
    for j in range(n): # ind
        ind = j-i
        if ind < 0: ind+=n
        # xcost = i*x
        next_a = al[ind]
        if curr_mins[j] > next_a:
            curr_mins[j] = next_a
        cost = curr_mins[j]
        curr_i_ans += cost
    ans = min(ans, curr_i_ans+i*x)

print(ans)
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
m = abs(a[n])
ans, ps = [], []
for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
if m != 1:
	ps.append(m)
if n == 0:
	print(*ps, sep="\n")
	exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)
		elif mods[0] == 1:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 1:
					ng = True
					break
			if not ng:
				print(p)

### FIXED CODE ###

import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and n != 0:
	ps.append(m)
#print(ps)
g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")
N = int(input())
a = list(map(int,input().split()))

cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]

dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

def cal(i,j):
    if dp[i][j] == -1:
        dp[i][j] = cum[j]-cum[i-1]-min(cal(i+1,j),cal(i,j-1))
    return dp[i][j]

print(2*cal(0,N-1)-cum[N-1])

### FIXED CODE ###

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

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(i, N):
        dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])

print(dp[0][N-1])
a=sorted(list(map(int,input().split()))
print(a[0]+a[1])

### FIXED CODE ###

a=sorted(list(map(int,input().split())))
print(a[0]+a[1])
N=list(map(int,input().split()))
n=N[0]
m=N[1]
A = []
for i in range(m):
  array = list(map(int,input().split()))
  array.sort()
  A.append(array)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

X=get_unique_list(A)

import collections

t = map(tuple,X)
counted = collections.Counter(t)
mode=counted.most_common()[0][0]

c=1
for j in range(len(X)):
  if mode[0] in X[j]:
    c+=1
 
    
print(c)

  
  



### FIXED CODE ###

class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)
import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    print(t)
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
n=int(input())
a=int(input())
b=int(input())
if n==1:
  print("Hello World")
else:
  print(a+b)

### FIXED CODE ###

n=int(input())
if n==2:
  a=int(input())
  b=int(input())
if n==1:
  print("Hello World")
else:
  print(a+b)
n = input()
a = n.index("A")
n = len(n) - n[::-1].index("Z") - 1
print(len(n[a:n+1]))

### FIXED CODE ###

n = input()
print(n.rfind("Z") - n.find("A") + 1)
# coding: utf-8
# Your code here!
import numpy as np
 
N, M, Q = map(int, input().rstrip().split(' '))
 
memo = np.zeros((N, N)).astype(int)
 
for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    memo[:p, q-1:] += 1
 
for i in range(Q):
    p, q = map(int, input().rstrip().split(' '))
    print(memo[p-1][q-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!

N, M, Q = map(int, input().rstrip().split(' '))

count = [[0] * (N + 1) for _ in range(N+1)]
memo = [[0] * (N + 1) for _ in range(N+1)]

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    count[p][q] += 1

for i in range(1,N+1):
    for j in range(1,N+1):
        memo[i][j] = count[i][j] + memo[i-1][j] + memo[i][j-1] - memo[i-1][j-1]

for i in range(Q):
    p, q = map(int, input().rstrip().split(' '))
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
def main():
  N, M = map(int, input().split())

   def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr.append([i, cnt])
        if temp != 1:
            arr.append([temp, 1])

        if arr == [] and n != 1:
            arr.append([n, 1])

        return arr

    mod = 10**9 + 7

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range(2, N+100 + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    primes = factorization(M)
    # 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））

    ans = 1

    for p, cnt in primes:
        tmp = cmb(N+cnt-1, N-1, mod)
        ans *= tmp
        ans %= mod

    print(ans)


main()


### FIXED CODE ###

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


primes = factorization(M)
# 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））

if N == 1 or M == 1:
    print(1)
    exit(0)
ans = 1
for p, cnt in primes:
    tmp = 0
    for i in range(1, min(cnt, N)+1):
        tmp += cmb(N, i, mod) * cmb(cnt-1, i-1, mod)
        #print(tmp, p, cnt, i)
        tmp %= mod
    ans *= tmp
    ans %= mod

print(ans)
x = input()
digits = [int(a) for a in x]
fx = sum(digits)
print("Yes" if x % fx == 0 else "No")



### FIXED CODE ###

x_str = input()
x = int(x_str)
digits = [int(a) for a in x_str]
fx = sum(digits)
if x % fx == 0:
  print("Yes")
else:
  print("No")
count=int("K")
print('ACL'*count)

### FIXED CODE ###

print('ACL'*int(input()))
S=input()
T=input()
L=len(S)

dds=defaultdict(int)
ddt=defaultdict(int)

for i in range(L):
    s=S[i]
    t=T[i]
    if dds[s]==0:
        dds[s]=t
    else:
        if dds[s]!=t:
            print("No")
            exit()
    if ddt[t]==0:
        ddt[t]=s
    else:
        if ddt[t]!=s:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

from collections import defaultdict

S=input()
T=input()
L=len(S)

dds=defaultdict(int)
ddt=defaultdict(int)

for i in range(L):
    s=S[i]
    t=T[i]
    if dds[s]==0:
        dds[s]=t
    else:
        if dds[s]!=t:
            print("No")
            exit()
    if ddt[t]==0:
        ddt[t]=s
    else:
        if ddt[t]!=s:
            print("No")
            exit()
print("Yes")
n , m = map(int,input().split())
d = {}
for i in range(m):
    xi, yi, zi = map(int,input().split())
    if xi in d:
        d[xi] += [yi]
    else:
        d[xi] = [yi]
    if yi in d:
        d[yi] += [xi]
    else:
        d[yi] = [xi]

def f(x):
    global v
    v.remove(x)
    if x in d:
        for k in d[x]:
            if k in v:
                f(k)


v = [i+1 for i in range(n)]
count = 0
while len(v) > 0:
    f(v[0])
    count += 1
print(count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
n , m = map(int,input().split())
g = [i for i in range(n)]
def find(x):
    if g[x] == x:
        return x
    g[x] = find(g[x])
    return g[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x!=y:
        g[x] = y

for i in range(m):
    xi,yi,zi = map(int,input().split())
    union(xi-1,yi-1)

ans = 0
for i in range(n):
    if find(i) == i:
        ans += 1
print(ans)
# coding: utf-8
import sys
sysread = sys.stdin.readline
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]

    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1
        
        if parent == None:
            dp[node].append(A[node])
        else:
            for val in dp[parent][1:]:
                dp[node].append(val)
            for i, val in enumerate(dp[node][1:], 1):
                if val > A[node]:
                    dp[node][i] = A[node]
                    break
            if dp[node][-1] < A[node]:
                dp[node].append(A[node])
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)
    
    for i in range(1, N+1):
        try:
            s = dp[i][1:].index(float('inf'))
            print(s)
        except:
            print(len(dp[i][1:]))


if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            idx = bin_search(dp, a)
            if dp[idx] == float('inf'):
                actions.append((idx, dp[idx], a, 1))
                ddp2[0] += 1
            else:
                actions.append((idx, dp[idx], a, 0))
            dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()
import sys


def main():
    t = input()
    s = input()

    appear_pos = {}  # 文字が出てくる場所
    for idx, T in enumerate(t):
        if T not in appear_pos:
            appear_pos[T] = [idx]
        else:
            appear_pos[T].append(idx)

    search_idx = {}
    for key in appear_pos.keys():
        search_idx[key] = 0

    loop_count = 0
    find_idx = 0
    for S in s:
        if S not in appear_pos:
            print(-1)
            sys.exit()

        if len(appear_pos[S]) > search_idx[S]:
            idx_new = appear_pos[S][search_idx[S]]
        else:
            idx_new = appear_pos[S][search_idx[0]]
        search_idx[S] += 1

        if idx_new > find_idx:
            find_idx = idx_new
            continue

        # 初期化
        find_idx = idx_new
        loop_count += 1
        for key in appear_pos.keys():
            search_idx[key] = 0

    print(find_idx+loop_count*len(t)+1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    t = input()
    s = input()

    appear_pos = {}  # 文字が出てくる場所
    for idx, T in enumerate(t):
        if T not in appear_pos:
            appear_pos[T] = [idx]
        else:
            appear_pos[T].append(idx)

    search_idx = {}
    for key in appear_pos.keys():
        search_idx[key] = -1

    loop_count = 0
    find_idx = -1
    for S in s:
        if S not in appear_pos:
            print(-1)
            sys.exit()

        while True:
            search_idx[S] += 1
            if len(appear_pos[S]) == search_idx[S]:
                # 次のループに移動する
                loop_count += 1
                for key in appear_pos.keys():
                    search_idx[key] = -1
                find_idx = appear_pos[S][0]
                break

            idx_new = appear_pos[S][search_idx[S]]
            if idx_new > find_idx:
                find_idx = idx_new
                break

    print(find_idx+loop_count*len(t)+1)


if __name__ == '__main__':
    main()
import math
a,b = map(int,input().split())
print(int(math.ceil((a+b)/2,0)))

### FIXED CODE ###

import math
a,b = map(int,input().split())
print(int(math.ceil((a+b)/2)))
# https://atcoder.jp/contests/abc060/tasks/abc060_a

import itertools
import collections
import bisect

def main():
    A, B, C = map(int, input().split())
    print('YES' if A[-1] == B[0] and B[-1] == C[0] else 'NO')

if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc060/tasks/abc060_a

import itertools
import collections
import bisect

def main():
    A, B, C = input().split()
    print('YES' if A[-1] == B[0] and B[-1] == C[0] else 'NO')

if __name__ == '__main__':
    main()
N = int(input())
T,A = map(int,input().split())
h = list(map(int,input().split()))
#iは番号
ans = 0
base = T - 0.06*h[0]
for i,n in enumerate(h):
    if(i==0):
        pass
    tem = T - 0.006*n
    if(abs(tem - A)<abs(base - A)):
        base = tem
        ans = i+1
    else:
        ans = 1
print(ans)


### FIXED CODE ###

x, y = map(int,input().split())
y = 1/2 * y
ans = int(x + y)
print(ans)
import math

R = int(input())

print(2 * math.pai * R)

### FIXED CODE ###

R = int(input())

print(2*3.141592*R)
from collections import Counter

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

one = sorted(Counter([v[i] for i in range(0, n, 2)]).items(), key=lambda x: x[1], reverse=True)
two = sorted(Counter([v[i] for i in range(1, n, 2)]).items(), key=lambda x: x[1], reverse=True)

print(one, two)
if one[0][0] != two[0][0]:
	print(n - one[0][1] - two[0][1])
else:
	if len(one) == 1 and len(two) == 1:
		print(n // 2)
	elif len(one) == 1:
		print(n // 2 - two[1][1])
	elif len(two) == 1:
		print(n // 2 - one[1][1])
	else:
		print(min(n - one[0][1] - two[1][1]), n - one[1][1] - two[0][1])

### FIXED CODE ###

from collections import Counter

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

one = sorted(Counter([v[i] for i in range(0, n, 2)]).items(), key=lambda x: x[1], reverse=True)
two = sorted(Counter([v[i] for i in range(1, n, 2)]).items(), key=lambda x: x[1], reverse=True)

#print(one, two)
if one[0][0] != two[0][0]:
	print(n - one[0][1] - two[0][1])
else:
	if len(one) == 1 and len(two) == 1:
		print(n // 2)
	elif len(one) == 1:
		print(n // 2 - two[1][1])
	elif len(two) == 1:
		print(n // 2 - one[1][1])
	else:
		print(min(n - one[0][1] - two[1][1], n - one[1][1] - two[0][1]))
import math

def prime(x):
    if x==1:
        prime=False
    else:
        prime=True
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i==0:
                prime=False
                break
    return prime

def count_prime(N):
    prime_self=False
    
    if prime(N):
        prime_self=True
        p=[]
    else:    
        p=[0 for n in range(int(math.sqrt(N)+1))]
        end=False
        while N>1 and end==False:
            rtN=int(math.sqrt(N)+1)
            for i in range(2,rtN):
                if N%i==0 and prime(i):
                    p[i]+=1
                    N=N//i
                    break
            if prime(N):
                p[N]+=1
                end=True
    return p,prime_self

def main():
    N=int(input())
    p=count_prime(N)[0]
    cnt=0
    for n in range(len(p)):
        num=1
        while p[n]>=1:
            p[n]-=num
            if p[n]>=0:
                cnt+=1
            num+=1
    if count_prime(N)[1]:
        cnt+=1
    print(cnt)
        
if __name__=="__main__":
    main()
    

### FIXED CODE ###

import math

def prime(x):
    if x==1:
        prime=False
    else:
        prime=True
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i==0:
                prime=False
                break
    return prime

def count_prime(N):
    p=[0 for n in range(int(math.sqrt(N)+1))]
    
    if prime(N):#初期値が素数の場合
        big_prime=True
        
    else:#初期値が素数でない場合
        big_prime=False
        rtN_init=int(math.sqrt(N)+1)
        
        #素因数分解。ルートＮまでの範囲で素因数を探す。見つかったらpの素因数インデックスを++
        while N>1:
            #素数がルートNを超える場合
            if prime(N) and N>rtN_init:
                big_prime=True
                break
            else:
                for i in range(2,rtN_init):
                    if N%i==0 and prime(i):
                        p[i]+=1
                        N=N//i
                        break
    return p,big_prime

def main():
    N=int(input())
    p,q=count_prime(N)
    cnt=0
    
    for n in range(len(p)):
        num=1
        while p[n]>=1:
            p[n]-=num
            if p[n]>=0:
                cnt+=1
                num+=1
    if q==True:
        cnt+=1
    print(cnt)
        
if __name__=="__main__":
    main()