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

N, M = [int(x) for x in input().split()]

f = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    i, j = [int(x) for x in input().split()]
    f[j - 1][i - 1] = 1

ans = 0
for x in range(1, N):
    if sum(f[x]) == 0:
        ans += 1

print(ans)

### FIXED CODE ###

from typing import Dict, List

N, M = [int(x) for x in input().split()]

class UnionFind:
    def __init__(self, num_node: int):
        self.__parent_index = [x for x in range(num_node)]
        self.__tree_rank = [1] * num_node

    def __is_root(self, index: int) -> bool:
        return self.__parent_index[index] == index

    def root(self, index: int) -> int:
        """Find root index."""
        while not self.__is_root(index):
            index = self.__parent_index[index] = self.root(self.__parent_index[index])
        return index

    def unite(self, x: int, y: int) -> bool:
        """Unite two trees."""
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        if self.__tree_rank[x] < self.__tree_rank[y]:
            x, y = y, x

        self.__tree_rank[x] += self.__tree_rank[y]
        self.__parent_index[y] = x

        return True

    def groups(self) -> Dict[int, List[int]]:
        __groups: Dict[int, List[int]] = {}
        for node, parent in enumerate(self.__parent_index):
            __root = self.root(parent)
            if __groups.get(__root) is None:
                __groups[__root] = [node]
            else:
                __groups[__root].append(node)

        return __groups

uni = UnionFind(N)
for i in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    uni.unite(a, b)

print(len(uni.groups()) - 1)
### BUGGY CODE ###

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

count = 0
list00 = []
for i in range(0,n):
  if a[i] in list00:
    count = count
  else:
    count = count + 1
    list00.append(a[i])
if count == n:
  print('YES')
else:
  print('NO')
  

### FIXED CODE ###

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

count = 0
list00 = sorted(a)
for i in range(1, n):
  if list00[i-1] == list00[i]:
    count = count*0
  else:
    count = count + 1

if count == n-1:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
#print(ls)
for i in range(M):
  x=max(ls)
  y=x//2
  ls[ls.index(x)]=y
print(sum(ls))


### FIXED CODE ###

import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)
### BUGGY CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

    def factorization(n):
        ret = set()
        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
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 1.5:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
x = []
y = []
for i in range(q):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
t = []
for i in range(n):
    tmps = s[:i+1]
    t.append(tmps.count("AC"))
for i in range(q):
    ans = t[y[i]-1] - t[x[i]-1]
    print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
x = []
y = []
for i in range(q):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1) 

t = [0]*n

for i in range(n-1):
    if s[i+1] == "C" and s[i] == "A":
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]
for i in range(q):
    ans = t[y[i]-1] - t[x[i]-1]
    print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  print(S[l - 1: r].count('AC'))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])
### BUGGY CODE ###

S=str(input())
s=[]
c1=0
c0=0
for i in range(len(S)):
  s.append(S[i])
  if S[i]=='0':
    c0+=1
  else:
    c1+=1
c=0
while min(c0,c1)>0:
  for i in range(len(s)-1):
    if s[i:i+2]==['1','0'] or s[i:i+2]==['0','1']:
      c0-=1
      c1-=1
      s.remove(s[i])
      s.remove(s[i])
      c+=1
      break
print(2*c)

### FIXED CODE ###

S=str(input())
s=[]
c1=0
c0=0
for i in range(len(S)):
  s.append(S[i])
  if S[i]=='0':
    c0+=1
  else:
    c1+=1
print(2*min(c0,c1))
### BUGGY CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
for i in range(len(object)):
   if object[i][0] in cand_h and object[i][1] in cand_w:
      c += 1
print(ans - (c == p))

### FIXED CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
cand_h = set(cand_h)
cand_w = set(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))
### BUGGY CODE ###

h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
inf=10**9
dp=[inf]*(h+10**5)
dp[0]=0
#dp[i]=モンスターの体力をi減らすのに魔力が最低でいくつ必要か
for i in range(h):
    for a,b in l:
        dp[i+a]=min(dp[i+a],dp[i]+b)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)

### FIXED CODE ###

h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
inf=10**9
dp=[inf]*(h+10**5)
dp[0]=0
#dp[i]=モンスターの体力をi減らすのに魔力が最低でいくつ必要か
for i in range(h):
    for a,b in l:
        dp[i+a]=min(dp[i+a],dp[i]+b)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo[x]:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = [False]*(N+1)
count = dfs(0)
print(count%1000000007) 



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N:
    return 0
  if memo[x] >= 0:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = [-1]*(N+1)
for ai in a:
  memo[ai] = 0
count = dfs(0)
print(count%1000000007)
### BUGGY CODE ###

K = int(input())

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

for i in range(K):
    que.pop(0)
    temp = que[0]
    if temp % 10 == 0:
        que.append(temp*10+(temp % 10))
        que.append(temp*10+(temp % 10)+1)
    elif temp % 10 == 9:
        que.append(temp*10+(temp % 10)-1)
        que.append(temp*10+(temp % 10))
    else:
        que.append(temp*10+(temp % 10)-1)
        que.append(temp*10+(temp % 10))
        que.append(temp*10+(temp % 10)+1)


print(que[0])


### FIXED CODE ###

K = int(input())

que = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(K):
    temp = que[i]
    if i == K-1:
        print(que[i])
        break
    mod = temp % 10
    if mod == 0:
        que += [temp*10+(mod), temp*10+(mod)+1]
    elif temp % 10 == 9:
        que += [temp*10+(mod)-1, temp*10+(mod)]
    else:
        que += [temp*10+(mod)-1, temp*10+(mod), temp*10+(mod)+1]
### BUGGY CODE ###

import sys
s=input()
A,B =map(int,input().split())
table=[[] for i in range(2)]#0が横1が縦
t = 0
k=0
for i in range(len(s)):
    if s[i]=='F':
        k+=1
    else:
        table[t].append(k)
        t=(t+1)%2
        k=0
table[t].append(k)
L=len(s)
Lx=[set() for i in range(len(table[0]) +1)]
Ly=[set() for i in range(len(table[1]) +1)]
Lx[0].add(0)
Ly[0].add(0)
for i in range(len(table[0])):
    x = table[0][i]
    if i==0:
        Lx[1].add(x)
        continue
    for a in Lx[i]:
        if -L<=a+x<=L:
            Lx[i+1].add(a+x)
        if -L<=a-x<=L:
            Lx[i+1].add(a-x) 
flag=True
for a in Lx[len(table[0])]:
    if a==A:
        flag =False
if flag:
    print('No')
    sys.exit()
    
for i in range(len(table[1])):
    x = table[1][i]
    for a in Ly[i]:
        if -L<=a+x<=L:
            Ly[i+1].add(a+x)
        if -L<=a-x<=L:
            Ly[i+1].add(a-x)
flag=True
for a in Ly[len(table[1])]:
    if a==B:
        flag =False
if flag:
    print('No')
    sys.exit()
    
print('Yes')


### FIXED CODE ###

import sys
s=input()
A,B =map(int,input().split())
table=[[] for i in range(2)]#0が横1が縦
t = 0
k=0
for i in range(len(s)):
    if s[i]=='F':
        k+=1
    else:
        table[t].append(k)
        t=(t+1)%2
        k=0
table[t].append(k)
L=len(s)
Lx=[set() for i in range(len(table[0]) +1)]
Ly=[set() for i in range(len(table[1]) +1)]
Lx[0].add(0)
Ly[0].add(0)
for i in range(len(table[0])):
    x = table[0][i]
    if i==0:
        Lx[1].add(x)
        continue
    for a in Lx[i]:
        if -L<=a+x<=L:
            Lx[i+1].add(a+x)
        if -L<=a-x<=L:
            Lx[i+1].add(a-x) 
flag=True
for a in Lx[len(table[0])]:
    if a==A:
        flag =False
if flag:
    print('No')
    sys.exit()
    
for i in range(len(table[1])):
    x = table[1][i]
    for a in Ly[i]:
        if -L<=a+x<=L:
            Ly[i+1].add(a+x)
        if -L<=a-x<=L:
            Ly[i+1].add(a-x)
flag=True
for a in Ly[len(table[1])]:
    if a==B:
        flag =False
if flag:
    print('No')
    sys.exit()
    
print('Yes')
### BUGGY CODE ###

n,k=map(int,input().split())
s=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        s.append(j)

dp=[0]*n
dp[0]=1

smax=max(s)

for i in range(0,n):
    for j in range(max(0,i-smax),i):
        if i-j in s:
            dp[i]+=dp[j]

print(dp[n-1]%998244353)


### FIXED CODE ###

n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])
### BUGGY CODE ###

N, K = map(int,input().split())
while True:
    if abs(N-K) < N:
        N = abs(N-K)
    else:
        print(N)
        break




### FIXED CODE ###

N, K = map(int,input().split())
while True:
    if N%K == 0:
        print(0)
        break
    else:
        N=N%K
        N = min(N,abs(N-K))
        print(N)
        break
### BUGGY CODE ###

import numpy as np
h,n= map(int, input().split())
p = []
for i in range(n):
  z = list(map(int, input().split()))
  p.append(z)
dp = [0]*(h+1)
for i in range(1,h+1):
  dp[i] = min(dp[max(0,i-a)] + b for a,b in p)
print(min(dp[h:]))

### FIXED CODE ###

import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

from collections import deque

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

link = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    link[L[i][0]-1][L[i][1]-1] = 1
    link[L[i][1]-1][L[i][0]-1] = 1

checked = [-1 for _ in range(N)]
ans = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N):
        if link[now][i] == 1 and checked[i] == -1:
            checked[i] = checked[now] + 1
            ans[i] = now + 1
            d.append(i)

flag = False
for i in range(1, N):
    if ans[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(ans[i])

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
link = [[] for _ in range(N)]

for i in range(M):
    link[L[i][0]-1].append(L[i][1]-1)
    link[L[i][1]-1].append(L[i][0]-1)

checked = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if checked[link[now][i]] == -1:
            checked[link[now][i]] = now + 1
            d.append(link[now][i])


flag = False
for i in range(1, N):
    if checked[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(checked[i])
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(M))

    flag = 0
    for i in range(1, N):
        for a, b in A:
            if a == 1 and b == i:
                flag += 1
            elif a == i and b == N:
                flag += 1

        if flag == 2:
            ans = 'POSSIBLE'
            break
        else:
            flag = 0
    else:
        ans = 'IMPOSSIBLE'

    print(ans)

main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(M))

    if M == 1:
        print('IMPOSSIBLE')
        return

    relay = []
    for a, b in A:
        if a == 1:
            relay.append(b)
        elif b == N:
            relay.append(a)

    if len(relay) > len(set(relay)):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

main()
### BUGGY CODE ###

H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[0 for w in range(W + 2)] for h in range(H + 2)]
R = [[0 for w in range(W + 2)] for h in range(H + 2)]
D = [[0 for w in range(W + 2)] for h in range(H + 2)]
U = [[0 for w in range(W + 2)] for h in range(H + 2)] 
ans = 0
for i in range(H):
  S[i] = input()
  for j in range(W):
    if S[i][j] == '.':
      L[i + 1][j + 1] = L[i + 1][j] + 1
    if S[i][W - 1 - j] == '.':
      R[i + 1][W - j] = R[i + 1][W - j + 1] + 1
for j in range(W):
  for i in range(H):
    if S[i][j] == '.':
      U[i + 1][j + 1] = U[i][j + 1] + 1
    if S[H - 1 - i][j] == '.':
      D[H - i][j + 1] = D[H + 1 - i][j + 1] + 1
for i in range(1, H + 1):
  for j in range(1, W + 1):
    ans = max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3, ans)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[0 for w in range(W + 2)] for h in range(H + 2)]
R = [[0 for w in range(W + 2)] for h in range(H + 2)]
D = [[0 for w in range(W + 2)] for h in range(H + 2)]
U = [[0 for w in range(W + 2)] for h in range(H + 2)] 
ans = 0
for i in range(H):
  S[i] = input()
  for j in range(W):
    if S[i][j] == '.':
      L[i + 1][j + 1] = L[i + 1][j] + 1
    if S[i][W - 1 - j] == '.':
      R[i + 1][W - j] = R[i + 1][W - j + 1] + 1
for j in range(W):
  for i in range(H):
    if S[i][j] == '.':
      U[i + 1][j + 1] = U[i][j + 1] + 1
    if S[H - 1 - i][j] == '.':
      D[H - i][j + 1] = D[H + 1 - i][j + 1] + 1
for i in range(1, H + 1):
  for j in range(1, W + 1):
    ans = max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
prod = 1
for i in range(1,n+1):
  prod *= i
print(prod%(10**9+7))

### FIXED CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans*=i
  ans%=10**9+7
print(ans)
### BUGGY CODE ###

n = int(input())

al = []

for i in range(n):
    a = int(input())
    if al.count(a) > 0:
        al.remove(a)
    else:
        al.append(a)

print(len(al))


### FIXED CODE ###

n = int(input())
al = list(int(input()) for _ in range(n))

s = set()

for a in al:
    s ^= {a}

print(len(s))
### BUGGY CODE ###

import numpy as np

def solve():
    N = int(input())
    
    r = 1e12
    for i in range(N - 1, int(np.sqrt(N)) - 1, -1):
        if N % i == 0:
            r = min(r, (N / i - 1) + (i - 1))
            
    
    print(int(r))

solve()

### FIXED CODE ###

import numpy as np

def solve():
    N = int(input())
    
    r = 1e12
    for i in range(1, int(np.sqrt(N)) + 1):
        if N % i == 0:
            r = min(r, (N / i - 1) + (i - 1))
            
    
    print(int(r))

solve()
### BUGGY CODE ###

#48b
a,b,x = map(int,input().split())
ans = 0
for _ in range(b-a+1):
    if a%x ==0:
        ans+=1
        a+=1
    else:
        a+=1
print(ans)

### FIXED CODE ###

#48b
a,b,x = map(int,input().split())

A=a//x
B=b//x
C=0
if a%x==0:
    C+=1
print(B-A+C)
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=Counter(a)
t=[]
for _ in b.most_common():
  t.append(len([i for i in a if _[0]-1<i<_[0]+3]))
  t.append(len([i for i in a if _[0]-2<i<_[0]+2]))
  t.append(len([i for i in a if _[0]-3<i<_[0]+1]))
print(max(t))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=[i-1 for i in a]+a+[i+1 for i in a]
b=Counter(b).most_common(1)
print(b[0][1])
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
m = 1
for i in a:
    m = m * i
if m >10**18:
    print(-1)
else:
    print(m)

### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
m = 1
for i in a:
    m = m * i
    if m > 1000000000000000000:
        m = -1
        break
if 0 in a:
    print(0)
else:
    print(m)
### BUGGY CODE ###

import numpy as np


def main():
    N, W = map(int, input().split())

    w = []
    v = []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    dp = [[0] * (W+1) for i in range(N)]
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[-1][-1])
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# メイン関数
def main():
    # 入力データ
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    # dpテーブルの作成
    dp = [[0] * (W+1) for i in range(N)]
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    # 解答の出力
    print(dp[-1][-1])
    return

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

#整数の入力
N = int(input())
#スペース区切りの整数の入力リスト
A_list = list(map(int, input().split()))

ans = 0
for i in range(len(A_list)+1):
  ans = A_list.count(i+1)
  print(ans)

### FIXED CODE ###

#整数の入力
N = int(input())
#スペース区切りの整数の入力リスト
A_list = list(map(int, input().split()))

ans = 0
  
  
ans_list = [0]*N
  
for i in range(len(A_list)):
  #ans = A_list.count(i+1)
  ans_list[A_list[i]-1]+=1


for i in range(len(ans_list)):
  print(ans_list[i])
### BUGGY CODE ###

n = int(input())
ans = 0
for a in range(1, n+1):
    b=1
    while n-a*b>0:
        ans += 1
        b+=1
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

#C_Repsept
import math
K = int(input())
X = 0
kekka = -1
total = -1
for i in range(K): 
    X = X + pow(10,i) * 7
    kekka = X % K
    if kekka == 0:
        total = i+1
        break
# 出力
print(total)

### FIXED CODE ###

#C_Repsept
K = int(input())
if K % 7 == 0 :
    L = int( 9 * K / 7 )
else:
    L = 9 * K
X = 0
kekka = 1
total = -1
if L % 2 == 1:
    if L % 5 != 0:
        for i in range(L): 
            kekka = kekka * 10 % L
            if kekka == 1:
                total = i+1
                break
# 出力
print(total)
### BUGGY CODE ###

n, k = map(int, input().split())
if k > n:
    k = n
A = [int(i) for i in input().split()]
INF = 10 ** 12
dp = [INF] * n

dp[0] = 0
for i in range(1, n):
    for j in range(k + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(A[i] - A[i - j]))
    
print(dp[-1])

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
H = np.array(list(map(int, input().split())))
dp = np.zeros(n, dtype = int)

for i in range(1, n):
    s = max(i - k, 0)
    dp[i] = min(dp[s : i] + abs(H[i] - H[s : i]))
    
print(dp[-1])
### BUGGY CODE ###

#ずっとre
from fractions import gcd
from functools import reduce

def get_gcd(number_list):
    return reduce(gcd, number_list)

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

gcd_list = [get_gcd(Numbers[:i] + Numbers[i + 1:]) for i in range(N)]
    
print(int(max(gcd_list)))

### FIXED CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd

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


Left = [0] * (N + 1)
Right = [0] * (N + 1)

for i in range(N):
    Left[i + 1] = gcd(Left[i], A[i])
    Right[N - i - 1] = gcd(Right[N - i], A[N - i - 1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(Left[i], Right[i + 1]))
    
print(ans)