Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

WV = [tuple(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
R = N * 3

dp = [[-10**18] * (R + 1) for _ in range(N + 1)]
dp[0][0] = 0

for w, v in WV:
    w -= W0
    for n in range(N)[::-1]:
        for i in range(R)[::-1]:
            if i + w <= R:
                dp[n + 1][i + w] = max(dp[n + 1][i + w], dp[n][i] + v)

ans = 0
for n in range(N + 1):
    for w in range(R + 1):
        if n * W0 + w <= W:
            ans = max(ans, dp[n][w])
print(ans)


Fixed submission:
N, W = map(int, input().split())

items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append((v, w))

w0 = items[0][1]
itemGrp = [[] for _ in range(4)]
for v, w in items:
    itemGrp[w - w0].append(v)

for i in range(4):
    itemGrp[i].sort(reverse=True)

accItemGrp = []
for i in range(4):
    item = itemGrp[i]
    accValue = [0] * (len(item) + 1)
    for i in range(1, len(item) + 1):
        accValue[i] = accValue[i - 1] + item[i - 1]
    accItemGrp.append(accValue)

ans = 0
for n0 in range(len(itemGrp[0]) + 1):
    for n1 in range(len(itemGrp[1]) + 1):
        for n2 in range(len(itemGrp[2]) + 1):
            for n3 in range(len(itemGrp[3]) + 1):
                weight = (n0 + n1 + n2 + n3) * w0 + n1 + 2 * n2 + 3 * n3
                if weight <= W:
                    value = 0
                    for i, n in enumerate([n0, n1, n2, n3]):
                        value += accItemGrp[i][n]
                    ans = max(ans, value)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

def sol(S):
    ret = 0
    B = [S]
    for a in A[1:]:
        b = a
        if S * (S + b) > 0:
            b = (abs(S) + 1) * (1 if S < 0 else -1)
        if S + b == 0:
            b = b - 1 if b < 0 else b + 1
        ret += abs(b - a)
        S += b
        B.append(b)
    return ret

ans = min(
    sol(A[0]),
    sol(-A[0] // abs(A[0])) + abs(A[0]) + 1
)
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))

pos = 0
left = A[0]
if left <= 0:
    pos += 1 - left
    left = 1
for a in A[1:]:
    if left * (left + a) < 0:
        left += a
    else:
        if left + a == 0:
            if left < 0:
                left += a + 1
            else:
                left += a - 1
            pos += 1
        else:
            pos += abs(left + a) + 1
            if left < 0:
                left = 1
            else:
                left = -1

neg = 0
left = A[0]
if left >= 0:
    neg += left + 1
    left = -1
for a in A[1:]:
    if left * (left + a) < 0:
        left += a
    else:
        if left + a == 0:
            if left < 0:
                left += a + 1
            else:
                left += a - 1
            neg += 1
        else:
            neg += abs(left + a) + 1
            if left < 0:
                left = 1
            else:
                left = -1

print(min(neg, pos))
Buggy python submission (verdict: Time Limit Exceeded):
X, Y = map(int, input().split())

memo = [[[-1, -1] for _ in range(X + Y + 1)] for _ in range(X + Y + 1)]
def search(x, y, person):
    if x <= 1 and y <= 1:
        return False if person == 0 else True

    if x == 2 and y == 0 or x == 0 and y == 2:
        return True if person == 0 else False

    if memo[y][x][person] != -1:
        return memo[y][x][person]

    ret = False
    for i in range(2, x + 1, 2):
        ret |= search(x - i, y + i // 2, 1 if person == 0 else 0)
    for i in range(2, y + 1, 2):
        ret |= search(x + i // 2, y - i, 1 if person == 0 else 0)

    memo[y][x][person] = ret
    return ret

ans = search(X, Y, 0)
print('Alice' if ans else 'Brown')

Fixed submission:
X, Y = map(int, input().split())

if abs(X - Y) <= 1:
    print('Brown')
else:
    print('Alice')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M)[:: -1]:
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, i):
                isNess[j] = True
            break

ans += sum(isNess)
print(N - ans)

Fixed submission:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M):
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, right):
                isNess[j] = True

ans += sum(isNess)
print(N - ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

maxA = [0 for _ in range(N + 1)]
minA = [float('inf') for _ in range(N + 1)]

for i, a in enumerate(A):
    minA[i + 1] = min(minA[i], a)
for i, a in enumerate(reversed(A)):
    maxA[-1 - i] = max(maxA[-1 - (i - 1)], a)

maxProfit = 0
for i in range(1, N):
    if maxProfit < maxA[i + 1] - minA[i]:
        maxProfit = maxA[i + 1] - minA[i]

pairs = set([])
for i in range(1, N):
    if maxProfit == maxA[i + 1] - minA[i]:
        pairs.add((minA[i], maxA[i + 1]))

ans = 0
for minVal, maxVal in pairs:
    right = N - 1
    maxCount = 0
    while A[right] != maxVal:
        right -= 1
    for i in range(right):
        if A[i] == minVal:
            maxCount += 1
    left = 0
    minCount = 0
    while A[left] != minVal:
        left += 1
    for i in range(left, N):
        if A[i] == maxVal:
            minCount += 1
    ans += min(maxCount, minCount)

print(ans)

Fixed submission:
from collections import Counter

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

maxA = [0 for _ in range(N + 1)]
minA = [float('inf') for _ in range(N + 1)]

for i, a in enumerate(A):
    minA[i + 1] = min(minA[i], a)
for i, a in enumerate(reversed(A)):
    maxA[-1 - i] = max(maxA[-1 - (i - 1)], a)

maxProfit = 0
for i in range(1, N):
    if maxProfit < maxA[i + 1] - minA[i]:
        maxProfit = maxA[i + 1] - minA[i]

pairs = set([])
for i in range(1, N):
    if maxProfit == maxA[i + 1] - minA[i]:
        pairs.add((minA[i], maxA[i + 1]))

ans = len(pairs)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

tNow = 1
aNow = 1

for i in range(N) :
    t, a = map(int, input().split())
    n = 1
    while n * t < tNow or n * a < aNow :
        n += 1
    tNow = n * t
    aNow = n * a

print(tNow + aNow)

Fixed submission:
N = int(input())

tNow = 1
aNow = 1

for i in range(N) :
    t, a = map(int, input().split())

    n = max(-(-tNow // t), -(-aNow // a))

    tNow = n * t
    aNow = n * a

print(tNow + aNow)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)

dp = [[-float('inf') for _ in range(N + 1)] for _ in range(N + 1)]  # dp[ターン][パーを出せる回数] = score

dp[0][0] = 0

for turn in range(N) :
    for count in range(N + 1) :
        if count > turn :
            break
        dp[turn + 1][count + 1] = max(
            dp[turn + 1][count + 1],
            dp[turn][count] - (1 if S[turn] == 'p' else 0)
        )
        if count > 0 :
            dp[turn + 1][count - 1] = max(
                dp[turn + 1][count - 1],
                dp[turn][count] + (1 if S[turn] == 'g' else 0)
            )

ans = -float('inf')
for i in range(N + 1) :
    ans = max(ans, dp[N][i])
print(ans)

Fixed submission:
S = input()

count = 0
for s in S :
    if s == 'p' :
        count += 1

ans = -count + len(S) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)

dp = [[-float('inf') for _ in range(N + 1)] for _ in range(N + 1)]  # dp[ターン][パーを出せる回数] = score

dp[0][0] = 0

for turn in range(N) :
    for count in range(N + 1) :
        if count > turn :
            break
        dp[turn + 1][count + 1] = max(
            dp[turn + 1][count + 1],
            dp[turn][count] - (1 if S[turn] == 'p' else 0)
        )
        if count > 0 :
            dp[turn + 1][count - 1] = max(
                dp[turn + 1][count - 1],
                dp[turn][count] + (1 if S[turn] == 'g' else 0)
            )

ans = -float('inf')
for i in range(N + 1) :
    ans = max(ans, dp[N][i])
print(ans)

Fixed submission:
S = input()

count = 0
for s in S :
    if s == 'p' :
        count += 1

ans = -count + len(S) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

H, W, N = map(int, input().split())
V = set([tuple(map(int, input().split())) for _ in range(N)])
D = tuple(product((-1, 0, 1), repeat=2))

A = set()
for a, b in V:
    for h, w in D:
        if 2 <= a + h <= H - 1 and 2 <= b + w <= W - 1:
            A.add((a + h, b + w))

ans = [0] * 10
for a, b in A:
    cnt = 0
    for h, w in D:
        if (a + h, b + w) in V:
            cnt += 1
    ans[cnt] += 1

ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep='\n')


Fixed submission:
from collections import defaultdict

def sol():
    H, W, N = map(int, input().split())
    origin = defaultdict(int)

    ans = [0 for _ in range(10)]
    ans[0] = (H - 2) * (W - 2)

    def addBlack(h, w):
        ans[origin[(h, w)]] -= 1
        ans[origin[(h, w)] + 1] += 1
        origin[(h, w)] += 1

    for _ in range(N):
        h, w = map(int, input().split())

        for a in [-1, 0, 1]:
            for b in [-1, 0, 1]:
                if 2 <= h + a <= H - 1 and 2 <= w + b <= W - 1:
                    addBlack(h + a, w + b)

    for a in ans:
        print(a)

sol()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

class SlideMin:
    """
    スライド最小値\n
    各区間[ai, ai+leng]の最小値を取得する：O(n)\n
    self.que = [(i1, v1), (i2, v2), ..., (ik, vk)]\n
    i1 < ... < ik and v1 < ... < vk
    """
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

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

def sol(n):
    # n個前までの最小値
    B = A + A
    que = SlideMin(n + 1)
    ret = [10**18] * N
    for i, a in enumerate(B):
        que.update(i, a)
        ret[i % N] = min(ret[i % N], que.top()[1])
    return sum(ret) + n * X

ans = sum(A)
for i in range(N):
    ans = min(ans, sol(i))
print(ans)


Fixed submission:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def sol():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))

    B = A.copy()
    ans = sum(B)
    for magic in range(1, N):
        for i in range(N):
            B[i] = min(B[i], A[i - magic])
        ans = min(ans, sum(B) + X * magic)

    print(ans)

sol()
Buggy python submission (verdict: Runtime Error):
def sol():
    N = int(input())
    S = int(input())

    if N == S:
        print(N + 1)
        return

    def digitSum(n, b):
        if b < 0:
            return -1
        if n < b:
            return n
        return digitSum(n // b, b) + n % b

    for b in range(2, int(N**0.5 + 10)):
        if digitSum(N, b) == S:
            print(b)
            return

    for p in range(1, int(N**0.5 + 10)):
        b = (N - S) // p + 1
        if digitSum(N, int(b)) == S:
            print(int(b))
            return
    print('-1')
sol()

Fixed submission:
def sol():
    N = int(input())
    S = int(input())

    if N == S:
        print(N + 1)
        return

    def digitSum(n, b):
        if b < 2:
            return -1
        if n < b:
            return n
        return digitSum(n // b, b) + n % b

    for b in range(2, int(N**0.5) + 1):
        if digitSum(N, b) == S:
            print(b)
            return

    for p in range(int(N**0.5), 0, -1):
        b = (N - S) // p + 1
        if digitSum(N, b) == S:
            print(b)
            return
    print('-1')

sol()
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = int(input())

if N == S:
    print(N + 1)
    exit()

if S == 1:
    print(N)
    exit()

if S > N:
    print(-1)
    exit()

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

ans = float('inf')

for b in range(2, int(N**0.5) + 10):
    if f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if f(b, N) == S:
        ans = min(ans, b)

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = int(input())

if N == S:
    print(N + 1)
    exit()

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

ans = float('inf')

for b in range(1, int(N**0.5) + 100):
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

if ans == float('inf'):
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
N=input()
d=[input() for i in range(N)]
print(len(set(d)))

Fixed submission:
N=int(input())
d=[input() for i in range(N)]
print(len(set(d)))
Buggy python submission (verdict: Runtime Error):
input()
A=list(map(int,input().split()))
cnt=0
while all(a%2==0 for a in A):
  A=[a/2 for a in A]
  cnt++
print(cnt)

Fixed submission:
input()
A=list(map(int,input().split()))
cnt=0
while all(a%2==0 for a in A):
  A=[a/2 for a in A]
  cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
n = I()
dp = [0] * (500000)
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            pe = x**2 + y**2 + z**2 + x*y + y*z + z*x
            dp[pe] += 1
print(*dp[1:n+1],sep='\n')

Fixed submission:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
dp = [0] * (500000)
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            pe = x**2 + y**2 + z**2 + x*y + y*z + z*x
            dp[pe] += 1
print(*dp[1:n+1],sep='\n')
Buggy python submission (verdict: Runtime Error):
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n,m,k = readInts()
A = readInts()
B = readInts()
A = [0] + list(accumulate(A))
B = list(accumulate(B))
ans = 0
for i in range(len(A)):
    res = A[i]
    print('res:',A[i])
    print(B)
    r = bisect.bisect_right(B, k-res+1)
    print(r,'\n - - -\n')
    #print(i,r)
    if res <= k:
        ans = max(ans , i+r)
print(ans)


Fixed submission:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m,k = readInts()
A = [0] + list(accumulate(readInts()))
B = list(accumulate(readInts()))
ans = 0
import bisect
#print(B)
for i in range(len(A)):
    if A[i] > k:
        continue
    x = bisect.bisect_left(B,k - A[i] + 1)
    #print(x,)
    ans = max(ans,x+i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
A = readInts()
mi = float('inf')
for pa in combinations(A,k):
    nya = sum(pa)
    mi = min(mi,nya)
print(mi)


Fixed submission:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
A = readInts()
mi = float('inf')
A = sorted(A)

print(sum(A[:k]))
Buggy python submission (verdict: Time Limit Exceeded):
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
#n = 2*10**8
n = 20001002
prime = [] # i番目の素数
is_prime = [True] * (n+1)
p = 0 # 何番目か　0-indexed
is_prime[0] = False
is_prime[1] = False
ll = 0
#print('a')
for i in range(2,n+1):
    #ll += 1
    #print(i)
    if is_prime[i] == True:
        prime.append(i) # p番目の素数はiとなる
        p += 1
        # print(ll)
        # if p == 1000*ll:
        #     print(p)
        for j in range(2*i, n+1,i):
            is_prime[j] = False # その素数の倍数のやつ

#print(sieve(n,11000000))
#print(prime)
import math
def is_prime(n):
    for i in range(2,int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return n != 1 # 1の場合は除外

n = int(input())
if is_prime(n):
    print(1)
    exit()
cnt = 0
for v in prime:
    nya = v
    while n % v == 0:
        cnt += 1
        n //= v
        v *= nya
print(cnt)


Fixed submission:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
def soinsu(n):
    dic = defaultdict(int)
    i = 2
    while i*i <= n:
        if n%i == 0:
            dic[i] += 1
            n //= i
        else:
            i += 1
    if n!= 1:
        dic[n] += 1
    return dic
n = I()
dic = soinsu(n)
#print(dic)
cnt = 0
for k,v in dic.items():
    num = 1
    while v - num >= 0:
        cnt += 1
        v -= num
        num += 1
print(cnt)