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

N,M=map(int,input().split())
temp=[[0 for i in range(N)]for j in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    temp[a-1][b-1]=1
    temp[b-1][a-1]=1
ans=0
for i in range(N):
    ans=max(ans,sum(temp[i]))

print(ans+1)

### FIXED CODE ###

class UnionFind():
    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)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)
ans=0
for i in range(N):
    ans=max(ans,uf.size(i))

print(ans)
### BUGGY CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))

for t in range(k):
      ok=True
      b=[0]*n
      for i in range(n):
            left=max(0,i-a[i])
            b[left]+=1
            if i+a[i]+1 <= n-1:
                  right=i+a[i]+1
                  b[right]-=1
      for i in range(1,n):
            b[i]=b[i-1]+b[i]
      for i in range(n):
            if a[i]!=b[i]:
                  ok=False
            a[i]=b[i]
      if ok:
            break

print(*a)



### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))

for t in range(k):
      ok=True
      b=[0]*n
      for i in range(n):
            left=max(0,i-a[i])
            b[left]+=1
            if i+a[i]+1 <= n-1:
                  right=i+a[i]+1
                  b[right]-=1
      for i in range(1,n):
            b[i]=b[i-1]+b[i]
      for i in range(n):
            if a[i]!=b[i]:
                  ok=False
            a[i]=b[i]
      if ok==True:
            break

print(*a)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    dup = 0
    for i in range(1, n + 2):
        if a.count(i) == 2:
            dup = i

    first = a.index(dup)
    second = a[first + 1:].index(dup) + first + 1

    print(n)

    p = first
    q = (n + 1) - second - 1

    c1 = n + 1
    c2 = 1

    for i in range(2, n + 2):
        c1 *= (n + 1 - (i - 1))
        c1 %= MOD
        c1 *= pow(i, MOD - 2, MOD)
        c1 %= MOD
        c2 *= (p + q - (i - 2))
        c2 %= MOD
        c2 *= pow(i - 1, MOD - 2, MOD)
        c2 %= MOD
        print((c1 - c2) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    appeared = set()
    dup = 0

    for x in a:
        if x in appeared:
            dup = x
            break
        else:
            appeared.add(x)

    first = a.index(dup)
    second = a[first + 1:].index(dup) + first + 1

    print(n)

    p = first
    q = (n + 1) - second - 1

    c1 = n + 1
    c2 = 1

    for i in range(2, n + 2):
        c1 *= (n + 1 - (i - 1))
        c1 %= MOD
        c1 *= pow(i, MOD - 2, MOD)
        c1 %= MOD
        c2 *= (p + q - (i - 2))
        c2 %= MOD
        c2 *= pow(i - 1, MOD - 2, MOD)
        c2 %= MOD
        print((c1 - c2) % MOD)


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

N = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= a[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    ans = 1
    for i in range(N):
        ans *= a[i]
        if ans > 10 ** 18:
            break
    if ans > 10 ** 18:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
L = list( map( int, input().split() ) )
comb = []
for a in range(N):
  for b in range(1,N):
    if a == b:
      continue
    for c in range(2,N):
      if b == c or c == a:
        continue
      if (L[a] + L[b] > L[c]) and (L[b] + L[c] > L[a]) and (L[c] + L[a] > L[b]):
        comb.append( ' '.join( str(n) for n in sorted( [L[a],L[b],L[c]] ) ) )
print( len( set(comb) ) )

### FIXED CODE ###

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

import bisect
L=sorted(L)
comb = 0
for a in range(N-2):
    for b in range(1+a,N-1):
        posIndex = bisect.bisect_left(L, L[a] + L[b])
        comb += posIndex - b - 1 if posIndex != 0 else 0
print(comb)
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S[::-1]):
	a = a + (int(s) * (10 ** i))
	
	ans += A[a%m]
	A[a%m] += 1

print(ans)
	

### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()
S = S[::-1]

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S):
	a = a + (int(s) * pow(10,i,m))
	a %= m
	
	ans += A[a]
	A[a] += 1

print(ans)
### BUGGY CODE ###

s = input()
s = list(s)
i = 0
j = 0
flg =0

if len(s) >1:
    while(1):
        for i in range(0,len(s)):
            if i == len(s)-1:
                flg = 1
                break
            elif s[i] != s[i+1]:
                s.pop(i+1)
                s.pop(i)
                j+=2
                break
            elif len(s) == 2:
                flg = 1
                break
            
        if len(s) ==0 or flg==1:
            break
        
print(j)

### FIXED CODE ###

s = input()
a = s.count('1')
b = s.count('0')
print(min(a,b)*2)
### BUGGY CODE ###

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

score = [k-q for i in range(n)]
for i in a:
    for j in range(len(score)):
        if j == i-1:
            score[j] = score[j]+1
            pass

for i in score:
    if i <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

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

score = [k-q for i in range(n)]
for i in a:
    score[i-1] = score[i-1]+1
    

for i in score:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

from copy import copy
from collections import deque
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
first = deque(L)
count = 0
for i in range(N-2):
    l = first.popleft()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.popleft()
        n = len([i for i in second if i > l-m])
        if n > 0:
            count += n
        else:
            break
print(count)

### FIXED CODE ###

from copy import copy
from collections import deque
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
first = deque(L)
count = 0
for i in range(N-2):
    l = first.pop()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.pop()
        n = len(second) - bisect.bisect_right(second,l-m)
        if n > 0:
            count += n
        else:
            break
print(count)
### BUGGY CODE ###

s = [int(c) for c in input()]
dp = [[0] * 2019 for _ in range(len(s))]

for i,item in enumerate(s):
    dp[i][item] += 1
    for j in range(2019):
        tmp = (10 * j + item) % 2019
        dp[i][tmp] += dp[i-1][j]
#         if dp[i-1][j]!=0:
#             print(i, tmp, dp[i-1][j])
print(sum(dp[j][0] for j in range(len(dp))))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

import collections
s = [int(c) for c in input()]
tmp = 1
mod = 0
count = collections.defaultdict(int)
for i,num in enumerate(s[::-1]):
    mod = (tmp * num + mod) % 2019
    count[mod] += 1
    tmp *= 10
    tmp %= 2019
count[0] += 1
print(sum((item*(item-1)//2 for item in count.values())))
### BUGGY CODE ###

import itertools

def main():
    M = ['M','A','R','C','H']
    N = int(input())
    S = []
    cnt = 0
    for _ in range(N):
        S.append(input())
    for a,b,c in itertools.combinations(S,3):
        if a[0] == b[0] or b[0] == c[0] or a[0] == c[0]:
            continue
        if a[0] in M and b[0] in M and c[0] in M:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N = int(input())
    MARCH = ['M','A','R','C','H']
    S = [0] * len(MARCH)
    for _ in range(N):
        s = input()
        if not s[0] in MARCH:
            continue
        if s[0] == MARCH[0]: S[0] += 1
        elif s[0] == MARCH[1]: S[1] += 1
        elif s[0] == MARCH[2]: S[2] += 1
        elif s[0] == MARCH[3]: S[3] += 1
        elif s[0] == MARCH[4]: S[4] += 1
    cnt = 0
    for i in range(len(S)-2):
        for j in range(i+1,len(S)-1):
            for k in range(j+1,len(S)):
                cnt += S[i]*S[j]*S[k]
    print(cnt)

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

# -*- coding: utf-8 -*-

N = int(input())

list = [list(map(int,input().split())) for i in range(N)]

# sort
for i in range(len(list)):
    for j in range(i+1,len(list)):
        Ai, Bi = list[i]
        Aj, Bj = list[j]

#        pr_i = Bi - Ai
#        pr_j = Bj - Aj

        if Bi > Bj:
            list[i], list[j] = list[j], list[i]

#check
time = 0
result = True
for i in list:
    A, B = i
    time += A

#    print("work[{0}({1},{2})] time:{3}".format(i,A,B,time))

    if time > B:
        result = False
        break

message = "Yes" if result else "No"
print(message)


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

list = [list(map(int,input().split())) for i in range(N)]

# sort
list.sort(key=lambda x:x[1])
#check
time = 0
result = True
for i in list:
    A, B = i
    time += A

    #print("work[{0}({1},{2})] time:{3}".format(i,A,B,time))

    if time > B:
        result = False
        break

message = "Yes" if result else "No"
print(message)
### BUGGY CODE ###

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

import itertools

cnt = 0
for i in range(1, N+1):
    for v in itertools.combinations(X, i):
        if sum(v)/i==A:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter

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

X2 = [0]*N

for i in range(N):
    X2[i] = X[i] - A

C = Counter([0, X2[0]])

for x in X2[1:]:
    C2 = Counter()
    for s, c in C.items():
        C2[s+x] += c
    C += C2

print(C[0]-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from functools import reduce
import fractions


def gcd(*numbers):
  return reduce(fractions.gcd, numbers)


n = int(input())
lst = list(map(int, input().split()))
lst.sort()

v = 0
index = 0
# 2値の最大公約数を求める
for i in range(n):
  arr = lst[:i] + lst[i + 1:len(lst)]
  g = gcd(*arr)
  if g > v:
    v = g
    index = i

print(v)

### FIXED CODE ###

import fractions
from functools import reduce

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

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
  left[i + 1] = (fractions.gcd(left[i], a[i]))
  right[n - i - 1] = (fractions.gcd(right[n - i], a[n - 1 - i]))

ans = 0
for i in range(n):
  ans = max(ans, fractions.gcd(left[i], right[i + 1]))
print(ans)
### BUGGY 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():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [d[0] % m]
        d0 = [int(d[0] % m == 0)]
        for val in d[1:]:
            _d.append(_d[-1] + val % m)
            d0.append(d0[-1] + int(val % m == 0))


        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[n_rest - 1]
            d0_rest = d0[n_rest - 1]

        a_last = x + n_d * _d[-1] + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0[-1] + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

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
import numpy as np
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))
    d = np.array(d, dtype=np.uint64)

    def check(n ,x, m):
        _d = d % m
        d0 = d % m == 0
        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[:n_rest].sum()
            d0_rest = d0[:n_rest].sum()

        a_last = x + n_d * _d.sum() + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0.sum() + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(int(check(n, x, m)))

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

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def make_divisors(n):
    l_divs, u_divs = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            l_divs.append(i)
            if i != n // i:
                u_divs.append(n // i)
        i += 1
    return l_divs + u_divs[::-1]


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for k in c.keys():
        if c[k] > 1 and k in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    ans = [0] * (10 ** 6 + 1)

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            ans[a * i] += 1

    res = 0
    c = collections.Counter(A)
    for a in A:
        if ans[a] == 0 and c[a] == 1:
            res += 1

    print(res)



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

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)
M = int(input())
AB = tuple(tuple(map(int, input().split())) for _ in range(M))


parent = [-1] * (N + 1)
node = [1]
while node:
    s = node.pop()
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

pair = [-1] * M
for i, (a, b) in enumerate(AB):
    pa = set()
    pb = set()
    while a != 1:
        pa.add(a - 1)
        a = parent[a]
    while b != 1:
        pb.add(b - 1)
        b = parent[b]
    pair[i] = pa ^ pb

ans = pow(2, N - 1)

whole = set(range(1, N))
for bit in range(1, 1 << M):
    popcnt = 0
    inter = set()
    for i in range(M):
        if (bit >> i) & 1:
            popcnt += 1
            inter |= pair[i]
    x = N - len(inter) - 1
    if popcnt % 2 == 1:
        ans -= 2 ** x
    else:
        ans += 2 ** x

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)
M = int(input())
AB = tuple(tuple(map(int, input().split())) for _ in range(M))


parent = [-1] * (N + 1)
node = [1]
while node:
    s = node.pop()
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

pair = [-1] * M
for i, (a, b) in enumerate(AB):
    pa = set()
    pb = set()
    while a != 1:
        pa.add(a - 1)
        a = parent[a]
    while b != 1:
        pb.add(b - 1)
        b = parent[b]
    pair[i] = pa ^ pb

ans = pow(2, N - 1)

whole = set(range(1, N))
for bit in range(1, 1 << M):
    popcnt = 0
    inter = set()
    for i in range(M):
        if (bit >> i) & 1:
            popcnt += 1
            inter |= pair[i]
    x = N - len(inter) - 1
    if popcnt % 2 == 1:
        ans -= 2 ** x
    else:
        ans += 2 ** x

print(ans)
### BUGGY CODE ###

def checker(ded, da):
  for i in range(3):
    for j in range(2):
      if da[i][j] - ded[j] != da[i][2] - ded[2]:
        return False
  return True

def ma(da):
  for i in range(-100, 101):
    for j in range(-100, 101):
      for k in range(-100, 101):
        if checker([i, j, k], da):
          return False
  return True

da = [list(map(int,input().split())) for i in range(3)]
if not ma(da):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

def checker(ded, da):
  for i in range(3):
    for j in range(2):
      if da[i][j] - ded[j] != da[i][2] - ded[2]:
        return False
  return True

def ma(da):
  for i in range(-100, 101):
    for j in range(-100, 101):
      for k in range(-100, 101):
        if checker([i, j, k], da):
          return False
  return True

da = [list(map(int,input().split())) for i in range(3)]
if not ma(da):
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

from collections import deque

N, Q = map(int, input().split(' '))
tree = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    tree[a].append([a, b])
    tree[b].append([b, a])
val = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split(' '))
    val[p] += x
ans = [-1] * (N + 1)
ans[1] = val[1]
bfs = deque(tree[1])
while bfs:
    p,n = bfs.popleft()
    if ans[n] == -1:
        ans[n] = val[n]+ans[p]
        for i in tree[n]:
            bfs.append(i)
print(' '.join(list(map(str,ans[1:]))))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

memo = [0] * n

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

def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        memo[nv] += memo[v]
        dfs(nv, v)

dfs(0, -1)

print(*memo)
### BUGGY CODE ###

N = int(input())
S = input()
R_sum = [0]*N
G_sum = [0]*N
B_sum = [0]*N
rcnt = 0
gcnt = 0
bcnt = 0
cnt = 0
for c in S:
    if c == 'R':
        rcnt += 1
    elif c == 'G':
        gcnt += 1
    elif c == 'B':
        bcnt += 1
    R_sum[cnt] = rcnt
    G_sum[cnt] = gcnt
    B_sum[cnt] = bcnt
    cnt += 1

anssum = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]: continue
        clist = [S[i], S[j]]
        diff_idx = j - i

        if not ('R' in clist):
            anssum += (R_sum[N-1] - R_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'R':
                    anssum -= 1
        elif not ('G' in clist):
            anssum += (G_sum[N-1] - G_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'G':
                    anssum -= 1
        elif not ('B' in clist):
            anssum += (B_sum[N-1] - B_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'B':
                    anssum -= 1
print(anssum)


### FIXED CODE ###

N = int(input())
S = input()
R_sum = [0]*N
G_sum = [0]*N
B_sum = [0]*N
rcnt = 0
gcnt = 0
bcnt = 0
cnt = 0
for c in S:
    if c == 'R':
        rcnt += 1
    elif c == 'G':
        gcnt += 1
    elif c == 'B':
        bcnt += 1
    R_sum[cnt] = rcnt
    G_sum[cnt] = gcnt
    B_sum[cnt] = bcnt
    cnt += 1

anssum = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]: continue
        clist = [S[i], S[j]]
        diff_idx = j - i

        if not ('R' in clist):
            anssum += (R_sum[N-1] - R_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'R':
                    anssum -= 1
        elif not ('G' in clist):
            anssum += (G_sum[N-1] - G_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'G':
                    anssum -= 1
        elif not ('B' in clist):
            anssum += (B_sum[N-1] - B_sum[j-1])
            if diff_idx + j < N:
                if S[diff_idx + j] == 'B':
                    anssum -= 1
print(anssum)
### BUGGY CODE ###

def func(N):
    tmp=N
    arr=[]
    for i in range(2,N//2+1):
        if tmp%i==0:
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
            
    if tmp!=1 or arr==[]:
        arr.append([tmp, 1])
    return arr

N=int(input())
a=func(N)
ans=0
if a[0][0]==1:
        print(0)
        exit()
        
b=[1,3,6,10,15,21,28,36,45]
for i in a:
    for j in range(len(b)):
       if  i[1]<b[j]:
          ans+=j
          break
print(ans)

### FIXED CODE ###

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

N=int(input())
a=func(N)
ans=0
if a[0][0]==1:
        print(0)
        exit()
        
b=[1,3,6,10,15,21,28,36,45]
for i in a:
    for j in range(len(b)):
       if  i[1]<b[j]:
          ans+=j
          break
print(ans)
### BUGGY CODE ###

H, n = map(int, input().split())
A = []
B = []
for i in range(n):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

dp = [0 for i in range(H+1)]

for i in range(1, H+1):
	dp[i] = min(B[j]  if i < A[j]  else  dp[i - A[j]] + B[j]  for j in range(n))

print(dp[H])


### FIXED CODE ###

H, n = map(int, input().split())
A = []
B = []
for i in range(n):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

dp = [0 for i in range(H+1)]

for i in range(1, H+1):
	dp[i] = min(dp[i - A[j]] + B[j]  if A[j] <= i  else  B[j]  for j in range(n))

print(dp[H])