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

from itertools import combinations
n,k = list(map(int, input().split()))
k = min(n,k)
W = list(map(int,[input() for _ in range(n)]))
if k > 1: 
    P = 10001
    for b in combinations(range(1,n),k-1):
        s = 0
        Pi = 0
        for i in b:
            Pi = max(Pi, sum(W[s:i]))
            s = i
        P = min(P, max(Pi, sum(W[s:])))
    print(P)
else:
    print(sum(W))

### FIXED CODE ###

def checkCapacity(W,k,P):
    ws = 0
    cnt = 1
    for wi in W:
        ws += wi
        if ws > P:
            cnt += 1
            ws = wi
        if cnt > k: return False
    return True

if __name__=='__main__':
    n,k = list(map(int, input().split()))
    W = list(map(int,[input() for _ in range(n)]))
    Pmax = sum(W)
    Pmin = max(W)
    while Pmin < Pmax:
        P = (Pmax + Pmin) // 2
        if checkCapacity(W,k,P):
            Pmax = P
        else:
            Pmin = P + 1
    print(Pmax)
### BUGGY CODE ###

def block():
    block=0
    count=0
    while count<=(n-1):
        if h[count]>=1:
            block+=1
            count+=1
            while count<=(n-1):
                if h[count]>=1:
                    count+=1
                else:
                    count+=1
                    break
    return block
                
n=int(input())
h=list(map(int,input().split()))
ans=0
while sum(h)>0:
    bl=block()
    mini=min(h)
    ans+=mini*bl
    for i in range(n):
        h[i]-=mini
    
print(ans)

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
cnt = 0
 
while sum(h) > 0:
    min_h = max(h)
    i = h.index(min_h)
    #print(i)
    while i < len(h):
        if h[i] == min_h:
            h[i] -= 1
            i += 1
        else:
            break
    cnt += 1
 
print(cnt)
### BUGGY CODE ###

def calc(n, k, x):
    c = 0

    while x <= n:
        y = z = x

        while 0 < y:
            z = y

            while 0 < z:
                if x == y and y == z:
                    c += 1
                elif x == y or y == z:
                    c += 3
                else:
                    c += 6

                z -= k

            y -= k

        x += k

    return c

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

if k % 2 == 0:
    print(calc(n, k, k) + calc(n, k, k // 2))
else:
    print(calc(n, k, k))

### FIXED CODE ###

def calc(n, k, x):
    c = 0

    while x <= n:
        a  = (x - 1) // k
        c += 1 + 6 * (1 + a) * a // 2
        x += k

    return c

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

if k % 2 == 0:
    print(calc(n, k, k) + calc(n, k, k // 2))
else:
    print(calc(n, k, k))
### BUGGY CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_b = []
for i in range(0,n):
    list_b.append(list_a[i])
    list_b = list_b[::-1]
for i in range(0,n):
    list_b[i] = str(list_b[i])
print(" ".join(list_b))


### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_b = [0]*n
for i in range(0,n):
    if n % 2 == 1:
        if i % 2 == 0:
            list_b[(n-1)//2 - i//2] = list_a[i]
        else:
            list_b[(n-1)//2 + (i+1)//2] = list_a[i]
    else:
        if i % 2 == 1:
            list_b[n//2 - (i+1)//2] = list_a[i]
        else:
            list_b[n//2 + i//2] = list_a[i]

for i in range(0,n):
    list_b[i] = str(list_b[i])
print(" ".join(list_b))
### BUGGY CODE ###

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

edges = {i : [] for i in range(1, N+1)}
for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)

def dfs(n, count):
  # 定期便2つでは行けない
  if count == 3:
    return False
  if n == N:
    return True
  
  for edge in edges[n]:
    if dfs(edge, count + 1):
      return True
  
  return False

print("POSSIBLE" if dfs(1, 0) else "IMPOSSIBLE")

### FIXED CODE ###

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

edges = {i : [] for i in range(1, N+1)}
visited = [False for _ in range(N+1)]

for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)

def dfs(n, count):
  # 定期便2つでは行けない
  if count == 3:
    return False
  if n == N:
    return True
  visited[n] = True
  
  for edge in edges[n]:
    if visited[edge]:
      continue
    if dfs(edge, count + 1):
      return True
  
  return False

print("POSSIBLE" if dfs(1, 0) else "IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
s = list(map(int, list(input())))

numbers = set()

def exists(i, j, k, s):
  i_exists = False
  j_exists = False

  for ss in s:
    if i_exists == False and i == ss:
      i_exists = True
    elif j_exists == False and j == ss and i_exists:
      j_exists = True
    elif k == ss and i_exists and j_exists:
      return True
  return False

for i in range(0, 10):
  for j in range(0, 10):
    for k in range(0, 10):
      if exists(i, j, k, s):
        numbers.add(str(i) + str(j) + str(k))

# print(numbers)
print(len(numbers))


### FIXED CODE ###

n = int(input())
s = list(map(int, list(input())))

ary1 = [0 for i in range(10)]
ary2 = [[0 for i in range(10)] for j in range(10)]
ary3 = [[[0 for i in range(10)] for j in range(10)] for k in range(10)]

for ss in s:
  for i in range(10):
    for j in range(10):
      if ary1[i] == 1 and ary2[i][j] == 1:
        ary3[i][j][ss] = 1
  for i in range(10):
    if ary1[i] == 1:
      ary2[i][ss] = 1
  ary1[ss] = 1

numbers = set()

def exists(i, j, k, s):
  return ary3[i][j][k] == 1

for i in range(0, 10):
  for j in range(0, 10):
    for k in range(0, 10):
      if exists(i, j, k, s):
        numbers.add(str(i) + str(j) + str(k))

# print(numbers)
print(len(numbers))
### BUGGY CODE ###

import math

A, B, N = map(int, input().split(' '))
ans = 0
for x in range(N + 1):
    if not x % B: continue
    res = math.floor((A * x / B) - A * math.floor(x / B))
    ans = max(ans, res)
print(ans)


### FIXED CODE ###

import math

A, B, N = map(int, input().split(' '))
ans = 0
x = min(B, N + 1) - 1
ans = math.floor((A * x) / B) - A * (math.floor(x / B))
print(int(ans))
### BUGGY CODE ###

import numpy as np

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
Q=int(input())
B,C=map(int, input().split())
rep=[i for i, x in enumerate(A) if x == B]
for i in range(len(rep)):
    A[rep[i]]=C
ans=np.cumsum(A)
print(ans[-1])

for _ in range(Q-1):
    B,C=map(int, input().split())
    rep=[i for i, x in enumerate(A) if x == B]
    for i in range(len(rep)):
        A[rep[i]]=C
    ans[-1]+=(C-B)*len(rep)
    print(ans[-1])

### FIXED CODE ###

mod=pow(10,5)+2
N=int(input())
num=[0]*mod
ans=0
A=list(map(int, input().split()))
for i in range(N):
    num[A[i]]+=1
    ans+=A[i]
Q=int(input())
for i in range(Q):
    B,C=map(int, input().split())
    cnt=num[B]
    num[C]+=num[B]
    num[B]=0
    ans+=(C-B)*cnt
    print(ans)
### BUGGY CODE ###

from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)
input()
a=[int(i) for i in input().split()]
l=a[0]
for i in a:
    l=lcm(i,l)
s=0
for i in a:
    s+=(l//i)
print(s%1000000007)

### FIXED CODE ###

from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)
input()
a=[int(i) for i in input().split()]
l=a[0]
for i in a:
    l=lcm(i,l)
s=0
for i in a:
    s+=(l//i)
print(s%1000000007)
### BUGGY CODE ###

a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def cd(num):
    k = []
    if num%2 == 0:
        k.append(2) 
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k
 
def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True
 
 
gc = gcd(a,b)
c = cd(gc)
 
print(len(c))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
### BUGGY CODE ###

N = int(input())
A = set()
for i in range(N):
    A = A^{input()}
print(len(A))

### FIXED CODE ###

N = int(input())
A = set()
for i in range(N):
    A ^= {input()}
print(len(A))
### BUGGY CODE ###

X=int(input())
m = X
pf={}
if X == 1:
    pf[1] = 1
else:
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1

for p in pf.keys():
    i = 0
    while True:
        if pow(i,5) - pow(i-p,5) == X:
            print(i,i-p)
            exit()
        i+=1

### FIXED CODE ###

import math
X=int(input())
end=False
for i in range(-120,120):
    for j in range(-120,120):
        if pow(i,5) - pow(j,5) == X:
            print(i,j)
            end=True
            break
    if end==True:
        break
### BUGGY CODE ###

n=int(input())
s=list(input())

ans=[]
for i in range(n-1):
    i_set=set(s[i+1:])

    for j in i_set:
        j_ind=s.index(j)
        s_j=s[i+1:]
        j_set=set(s_j[s_j.index(j)+1:])
        # print(s_j)

        for k in j_set:
            k_ind=s.index(k)
            ans.append(s[i]+s[j_ind]+s[k_ind])
            # print(s[i]+s[j_ind]+s[k_ind])

print(len(set(ans)))

### FIXED CODE ###

n = int(input())

s = input()

ans = set()
for i in range(10):
    a = s.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = s.find(str(j), a+1)
        if b == -1:
            continue
        for k in range(10):
            if s.find(str(k), b+1) != -1:
                ans.add(str(i)+str(j)+str(k))
print(len(ans))
### BUGGY CODE ###

from collections import defaultdict
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))

dp = {0: 0}
for i in qqq:
    ndp = defaultdict(lambda: 10 ** 18)
    tmp_min_cost = 10 ** 18
    for j, cost in sorted(dp.items()):
        if cost >= tmp_min_cost:
            continue
        tmp_min_cost = cost
        if j < i:
            ndp[i] = min(ndp[i], cost)
            ndp[j] = min(ndp[j], cost + b)
        else:
            ndp[j] = min(ndp[j], cost + a)
    dp = ndp

print(min(dp.values()))


### FIXED CODE ###

from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    ndp = []
    s = bisect(dp, (i,))
    tmp_min = INF
    for j, cost in dp[:s]:
        cost += b
        ndp.append((j, cost))
        tmp_min = cost
    stay_cost = dp[s - 1][1]
    if tmp_min > stay_cost:
        ndp.append((i, stay_cost))
        tmp_min = stay_cost
    for j, cost in dp[s:]:
        cost += a
        if tmp_min > cost:
            ndp.append((j, cost))
            tmp_min = cost
    dp = ndp

print(dp[-1][1])
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
if k<x: a=a[:k]
if k<y: b=b[:k]
if k<z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if len(d)<k: d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
if k>x: a=a[:k]
if k>y: b=b[:k]
if k>z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if len(d)>k: d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

from collections import deque
import sys
input=sys.stdin.readline

N=int(input())

node=[[0] for i in range(N)]
#print(node)
q=[]
for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1,i])

q.sort(key=lambda x:x[0])

ans=0
for index in range(len(q)):
    frm,to,num=q[index][0],q[index][1],q[index][2]
    for i in range(1,10**6):
        if (i in node[frm]) or (i in node[to]):
            pass
        else:
            node[frm].append(i)
            node[to].append(i)
            q[index].append(i)
            ans=max(ans,i)
            break
            
print(ans)
q.sort(key=lambda x:x[2])
for item in q:
    print(item[3])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

q=[]

l=[[] for i in range(N)]

ans=[1]*N
ans[0]=0
#print(l)

for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1])
    l[a-1].append(b-1)

mx=0
for index,item in enumerate(l):
    color=1
    while item:
        temp=item.pop(-1)
        if color==ans[index]:
            color+=1
        ans[temp]=color
        color+=1
    mx=max(color-1,mx)

print(mx)
for _,item in q:
    print(ans[item])
### BUGGY CODE ###

def C_GreenBin():
    N = int(input())
    s = []
    for x in range(N):
        s.append(sorted(input()))
    result = 0
    s.sort()
    for i in range(0, N - 1):
        if s[i] != s[i+1]:
            continue
        for j in range(i + 1, N):
            if s[i] == s[j]:
                result += 1
            else:
                break
    print(result)
    
if __name__ == "__main__":
    C_GreenBin()

### FIXED CODE ###

def C_GreenBin():
    from collections import Counter
    N = int(input())
    s = []
    for x in range(N):
        list_tmp = sorted(input())
        s.append("".join(list_tmp))
    result = 0
    s_tmp = Counter(s)
    for x in s_tmp.values():
        if x > 1:
            result += ((x - 1) * x) // 2
    print(result)
    
if __name__ == "__main__":
    C_GreenBin()
### BUGGY CODE ###

from operator import itemgetter

N, M = map(int, input().split())
in_hand = list(map(int, input().split()))
in_hand.sort()

change_list = []

for line in range(M):
    change_count, change_number = map(int, input().split())

    change_list.append([change_count, change_number])


change_list.sort(key=itemgetter(1), reverse=True)


for change in change_list:
    in_hand.sort()
    for i in range(change[0]):
        if in_hand[i] < change[1]:
            in_hand[i] = change[1]
        else:
            break
    else:
        continue
    break

print(sum(in_hand))


### FIXED CODE ###

from operator import itemgetter

N, M = map(int, input().split())
in_hand = list(map(int, input().split()))
in_hand.sort()

change_list = []

for line in range(M):
    change_count, change_number = map(int, input().split())

    change_list.append([change_count, change_number])


change_list.sort(key=itemgetter(1), reverse=True)

index = 0
try:
    for change in change_list:
        for i in range(change[0]):
            if in_hand[i+index] < change[1]:
                in_hand[i+index] = change[1]
            else:
                break
        else:
            index += change[0]
            continue
        break
except:
    pass

print(sum(in_hand))
### BUGGY CODE ###

H, W = map(int, input().split())
q = []
a = {}
for y in range(H):
    l = input()
    for x in range(W):
        a[x, y] = l[x]
        if l[x] == '#':
            q.append((x,y))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1, qq[1]] == '.':
                a[qq[0] - 1, qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (W-1):
            if a[qq[0]+1, qq[1]] == '.':
                a[qq[0] + 1, qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0], qq[1]-1] == '.':
                a[qq[0], qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (H-1):
            if a[qq[0], qq[1]+1] == '.':
                a[qq[0], qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)


### FIXED CODE ###

h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '#'
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])


### FIXED CODE ###

import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

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

import math
N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
idx = []
for i in range(N):
  B[A[i]-1] += 1
  if B[A[i]-1] >= 2 and not A[i]-1 in idx:
    idx.append(A[i]-1)

def nCr (n, r):
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

Cs = []
C = []
Ctot = 0
for j in idx:
  if B[j]-1 >= 2:
    Cs.append(nCr(B[j]-1, 2))
  else:
    Cs.append(0)
  tmp = nCr(B[j], 2)
  C.append(tmp)
  Ctot += tmp

for i in range(N):
  current_idx = A[i]-1
  count = Ctot
  for k, j in enumerate(idx):
    if j == current_idx:
      count += Cs[k]
      count -= C[k]
  print(count)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
def nC2(n):
  return n*(n-1)//2
for i in range(N):
  B[A[i]-1] += 1
Ctot = 0
for i in range(N):
  Ctot += nC2(B[i])
for i in range(N):
  current_idx = A[i]-1
  if B[current_idx] == 1:
    count = Ctot
  else:
    count = Ctot + nC2(B[current_idx]-1) - nC2(B[current_idx])
  print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
#n個に分けてあげなきゃいけない
#できる限り平均的に分けてあげたほうがいいってことはわかる。
#大きい方から下って見つかって瞬間終わりにするほうが賢いかも
#候補のうち最大の数字は
i = int(m/n)
ans = 1
while i>=1:
    if m % i == 0 and m / i >= n:
        ans = i
        break
    i = i-1
print(ans)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
def check(n, LR):
  return 1 if all(l <= n <=r for l, r in LR) else 0

LR = []
for _ in range(M):
  LR.append([int(x) for x in input().split()])

print(sum(check(n, LR) for n in range(1, N+1)))


### FIXED CODE ###

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

def check(n, LR):
    return 1 if all(l <= n <=r for l, r in LR) else 0

L = 0
R = N
for _ in range(M):
    l, r = [int(x) for x in input().split()]
    if L < l:
        L = l
    if r < R:
        R = r

if L <= R:
    print(R - L + 1)
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(2147483647)

def solve():
    n = int(input())
    edge = [[] for _ in range(n)]
    for v in range(1,n):
        u = int(input())-1
        edge[u].append(v)

    dp = [None]*n
    def dfs(s):
        if dp[s] != None:
            return dp[s]
        if edge[s] == []:
            dp[s] = 0
            return 0
        tmp = []
        for v in edge[s]:
            tmp.append(dfs(v))
        dp[s] = max(1+i+x for i,x in enumerate(sorted(tmp,reverse=1)))
        return dp[s]
    print(dfs(0))
    
if __name__=='__main__':
    solve()



### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

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

#p_iの期待値は(1+p_i)/2で求められる
ans=0

expected_value=[0]*n
for i in range(n-k+1):
    if i==0:
        for j in range(i+n-1):
            expected_value[j]=(1+p_input[j])/2
    expected_value[i+k-1]=(1+p_input[i+k-1])/2
    ans = max(sum(expected_value[i:i+k]),ans)

print(ans)







### FIXED CODE ###

n,k = map(int,input().split())
p_input = list(map(lambda x:(int(x)+1)/2,input().split()))

#p_iの期待値は(1+p_i)/2で求められる
ans=0
sum_expected=[0]*(n-k+1)
for i in range(n-k+1):
    if i==0:
        sum_expected[0]=sum(p_input[:k])
    else:
        sum_expected[i]=sum_expected[i-1]-p_input[i-1]+p_input[i+k-1]

print(max(sum_expected))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
  first, last = map(int, input().split())
  print(s[first-1:last].count("AC"))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
s = input()
ac_list = [0]

for i in range(1, n):
  if s[i-1:i+1] == 'AC':
    ac_list.append(ac_list[i-1]+1)
  else:
    ac_list.append(ac_list[i-1])

for _ in range(q):
  first, last = map(int, input().split())
  print(ac_list[last-1] - ac_list[first-1])