Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = [A[i] - B[i] for i in range(N)]
ans = 0
if sum(A) < sum(B) :
    ans = -1
else :
    debt = []
    deposit = []
    for i in range(N) :
        if L[i] < 0 :
            debt.append(-L[i])
        elif L[i] > 0 :
            deposit.append(L[i])
        
    debt = sorted(debt)
    deposit = sorted(deposit,reverse=True)
    
    debt_duplicated = debt.copy()
    deposit_duplicated = deposit.copy()
    
    
    for i in range(len(debt)) :
        for j in range(len(deposit)) :
            if debt[i] <= deposit[j] :
                deposit[j] -= debt[i]
                debt[i] = 0
                break
            else :
                debt[i] -= deposit[j]
                deposit[j] = 0
    
    for i in range(len(debt)) :
        if debt[i] != debt_duplicated[i] :
            ans += 1
    for i in range(len(deposit)) :
        if deposit[i] != deposit_duplicated[i] :
            ans += 1

print(ans)
#print(debt)
#print(deposit)



Fixed submission:
N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = [A[i] - B[i] for i in range(N)]
ans = 0
if sum(A) < sum(B) :
    ans = -1
else :
    debt = []
    deposit = []
    for i in range(N) :
        if L[i] < 0 :
            debt.append(-L[i])
        elif L[i] > 0 :
            deposit.append(L[i])
        
    debt = sorted(debt)
    deposit = sorted(deposit,reverse=True)
    
    debt_duplicated = debt.copy()
    deposit_duplicated = deposit.copy()
    
    deposit_trash = []
    
    #print(debt)
    #print(deposit)
    
    for i in range(len(debt)) :
        
        while True :
            if debt[i] == 0 :
                break
            else :
                if debt[i] <= deposit[0] :
                    deposit[0] -= debt[i]
                    debt[i] = 0
                else :
                    debt[i] -= deposit[0]
                    deposit[0] = 0
                    deposit_trash.append(deposit.pop(0))
        
            
        
#        for j in range(len(deposit)) :
#            if debt[i] <= deposit[j] :
#                deposit[j] -= debt[i]
#                debt[i] = 0
#                break
#            else :
#                debt[i] -= deposit[j]
#                deposit[j] = 0
    deposit = deposit_trash + deposit
    for i in range(len(debt)) :
        if debt[i] != debt_duplicated[i] :
            ans += 1
    for i in range(len(deposit)) :
        if deposit[i] != deposit_duplicated[i] :
            ans += 1

print(ans)
#print(debt)
#print(deposit)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H,W = map(int,input().split())
MAP = [input() for i in range(H)]

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    if (ny,nx) in q :
                        continue
                    q.append((ny,nx))
                    
            ans += black*white

print(ans)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
MAP = [input() for i in range(H)]

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    if (ny,nx) in q :
                        continue
                    q.append((ny,nx))
                    
            ans += black*white

print(ans)
Buggy python submission (verdict: Runtime Error):
def flog(l) :
    if len(l) <= 1 :
        res = 0
    elif len(l) == 2 :
        res = abs(l[1]-l[0])
    else :
        a = abs(l[2]-l[0])
        b = abs(l[1]-l[0])
        if a <= b :
            res = a + flog(l[2:])
        else :
            res = b + flog(l[1:])
    return res

N = int(input())
H = list(map(int,input().split()))
H = list(reversed(H))

print(flog(H))


Fixed submission:
N = int(input())
L = list(map(int,input().split()))
dp = [0 for i in range(N)]
if N >= 3 :
    
    for i in range(1,3) :
        dp[i] = abs(L[i]-L[0])
    for i in range(3,len(dp)) :
        a = dp[i-1] + abs(L[i]-L[i-1])
        b = dp[i-2] + abs(L[i]-L[i-2])
        dp[i] = min(a,b)
    print(dp[N-1])
    #print(dp)

else :
    print(abs(L[-1]-L[0]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
L = [list(map(int,input().split())) for i in range(N)]
NOW = [0]*3
NEXT = [None]*3
for i in range(N) :
    NEXT[0] = max(NOW[1],NOW[2]) + L[0]
    NEXT[1] = max(NOW[2],NOW[0]) + L[1]
    NEXT[2] = max(NOW[0],NOW[1]) + L[2]    
    NOW = NEXT.copy()
print(max(NOW))


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

dp = [[0,0,0] for i in range(N+1)]
for i in range(N) :
    for j in range(3) :
        for k in range(3) :
            if j == k :
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + L[i][k])
print(max(dp[-1]))

Buggy python submission (verdict: Runtime Error):
N = int(input())
L = [[map(int,input().split())] for i in range(N)]

dp = [[0,0,0] for i in range(N+1)]
for i in range(N) :
    for j in range(3) :
        for k in range(3) :
            if j == k :
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + L[i][k])
print(ax(dp[-1]))



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

dp = [[0,0,0] for i in range(N+1)]
for i in range(N) :
    for j in range(3) :
        for k in range(3) :
            if j == k :
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + L[i][k])
print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N) :
    weight_i,value_i = L[i]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i)
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[N][W]

print(ans)


Fixed submission:
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for x in range(W+1)] for y in range(N+1)]

for i in range(N) :
    weight_i,value_i = L[i]
    for weight in range(W+1) :
        if weight-weight_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight-weight_i]+value_i, dp[i][weight])
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[N][W]
print(ans)


Fixed submission:
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)


Fixed submission:
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

upper = 10**5
dp = [float("inf") for i in range(upper+1)]
dp[0] = 0

for item in range(N) :
    weight_i,value_i = L[item]
    for value in range(upper, value_i-1, -1) :
        if dp[value - value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value - value_i] + weight_i)

for value in range(upper, -1, -1) :
    if dp[value] < float("inf") :
        ans = value
        break

print(ans)


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

max_size = 10**5
dp = [float("inf") for i in range(max_size+1)]
dp[0] = 0

for i in range(N) :
    weight,value = map(int,input().split())
    for j in range(max_size, value-1, -1) :
        if dp[j - value] + weight <= W :
            dp[j] = min(dp[j], dp[j-value] + weight)

for i in range(max_size, -1, -1) :
    if dp[i] < float("inf") :
        ans = i
        break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
dp = [[0 for j in range(len(T)+1)] for i in range(len(S)+1)]

for i in range(len(S)) :
    for j in range(len(T)) :
        if S[i] == T[j] :
            dp[i+1][j+1] = dp[i][j] + 1
        else :
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""

ind_x = len(T)
ind_y = len(S)

while ind_x * ind_y :
    if S[ind_y-1] == T[ind_x-1] :
        ans = S[ind_y-1] + ans
        ind_x -= 1
        ind_y -= 1
    elif dp[ind_y][ind_x] == dp[ind_y-1][ind_x] :
        ind_y -= 1
    else :
        ind_x -= 1
    

print(ans)


Fixed submission:
s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)


Fixed submission:
s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

H,W = map(int,input().split())
L = [input() for i in range(H)]

dxy = [(1,0),(0,1)]

cnt_list = [[float("inf") for x in range(W)] for y in range(H)]
cnt_list[0][0] = 1

q = collections.deque([(0,0)])

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny = y + dy
        nx = x + dx
        
        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue
        if L[ny][nx] == "#" :
            continue
        if cnt_list[ny][nx] < float("inf") :
            cnt_list[ny][nx] += cnt_list[y][x]
        else :
            cnt_list[ny][nx] = cnt_list[y][x]
            q.append((ny,nx))
ans = cnt_list[-1][-1]
if ans < float("inf") :
    ans %= 10**9+7
else :
    ans = 0

print(ans)


Fixed submission:
import collections

H,W = map(int,input().split())
L = [input() for i in range(H)]

dxy = [(1,0),(0,1)]

cnt_list = [[float("inf") for x in range(W)] for y in range(H)]
cnt_list[0][0] = 1

q = collections.deque([(0,0)])

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny = y + dy
        nx = x + dx
        
        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue
        if L[ny][nx] == "#" :
            continue
        if cnt_list[ny][nx] < float("inf") :
            cnt_list[ny][nx] += cnt_list[y][x]
        else :
            cnt_list[ny][nx] = cnt_list[y][x]
            q.append((ny,nx))
ans = cnt_list[-1][-1]
if ans < float("inf") :
    ans %= 10**9+7
else :
    ans = 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float,input().split()))

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

for i in range(N) :
    for j in range(i+1) :
        dp[i+1][j+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1 - P[i])

ans = 0
for i in range(N+1) :
    if i > N/2 :
        ans += dp[N][i]
print(ans)


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

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

for i in range(N) :
    for j in range(i+1) :
        dp[i+1][j+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1 - P[i])

ans = 0
for i in range(N+1) :
    if i > N/2 :
        ans += dp[N][i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A =list(map(int,input().split()))

dp = [[0]*N for i in range(N)]

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)


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

dp = [[0]*N for i in range(N)]

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

dp = [[0]*N for i in range(N)]
flag = [[0]*N for i in range(N)]

def f(left, right) :
    if flag[left][right] :
        return dp[left][right]
    elif left == right :
        flag[left][right] = 1
        dp[left][right] = A[left]
        return dp[left][right]
    else :
        flag[left][right] = 1
        dp[left][right] = max(A[left] - f(left+1, right), A[right] - f(left, right-1))
        return dp[left][right]

ans = f(0,N-1)
print(ans)


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

dp = [[0]*N for i in range(N)]

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

flag = [[0]*(N+1) for i in range(N+1)]

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

def f(left, right) :
    if flag[left][right] :
        return dp[left][right]
    elif left == right :
        return 0
    else :
        res = float("inf")
        for i in range(left, right) :
            res = min(res, f(left, i) + f(i+1, right))
        res += cA[right+1] - cA[left]
        dp[left][right] = res
        return res

ans = f(0,N-1)

print(ans)

#print(cA)

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

dp = [[10**18]*N for i in range(N)]

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

    dp[i-1][i-1] = 0

for d in range(1,N) :
    for i in range(N-d) :
        for cut in range(i, i+d) :
            dp[i][i+d] = min(dp[i][i+d], dp[i][cut] + dp[cut+1][i+d] + cA[i+d+1] - cA[i])

ans = dp[0][N-1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,C = map(int,input().split())


ans = 0
while True :
    if C > 0 :
        C -= 1
        ans += 1
        if B > 0 :
            B -= 1
            ans += 1
        elif A > 0 :
            A -= 1
        else :
            break
    elif B > 0 :
        B -= 1
        ans += 1
        if A > 0 :
            A -= 1
        else :
            break
    else :
        break
        
print(ans)

Fixed submission:
A,B,C = map(int,input().split())
ans = 0
if (A+B) >= C :
    ans += B+C
else :
    ans += min(B,C)*2
    ans += min(A,C)
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N,H,W = map(int,input().split())
L = []
for i in range(N) :
    a,b = map(int,input().split())
    if (a >= H) and (b >= W) :
        ans += 1
print(ans)


Fixed submission:
N,H,W = map(int,input().split())
L = []
ans = 0
for i in range(N) :
    a,b = map(int,input().split())
    if (a >= H) and (b >= W) :
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for i in range(N)]
odd = 0
for i in range(len(A)) :
    a = A[i]
    if a % 2 != 0 :
        odd += 1
        break
if odd == 1 :
    print("first")
else :
    print("second")
    

Fixed submission:
N,P = map(int,input().split())
from collections import Counter
def factorize(n) :
    d = Counter()
    m = 2
    while m*m <= n :
        while n%m == 0 :
            n //= m
            d[m] += 1
        m += 1
    if n > 1 :
        d[n] += 1
    return d

factors = factorize(P)
ans = 1
for k,v in factors.items() :
    a = v//N
    ans *= k**a
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
L = list(input())

ans = 0
for i in range(len(L)) :
    if L[i] == "B" :
        ans += L[i:].count("W")
print(ans)


Fixed submission:
L = list(input())
memo = L.count("W")
ans = 0
for i in range(len(L)) :
    if L[i] == "W" :
        memo -= 1
    else :
        ans += memo
print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
L = []
ans = []
for i in range(M) :
    L.append(list(map(int,input().split())))
    ans.append([None])

C = []
for i in range(N+1) :
    C.append([])

for i, (p,y) in enumerate(L) :
    C[p].append([y,i])

for p in range(N+1) :
    for i,(y,_) in enumerate(sorted(C[p])) :
        ans[_] = str(p).zfill(6) + str(i+1).zfill(6)
for i in range(N+1) :
    print(ans[i])


Fixed submission:
N,M = map(int,input().split())
L = []
ans = []
for i in range(M) :
    L.append(list(map(int,input().split())))
    ans.append([])

C = []
for i in range(N+1) :
    C.append([])

for i, (p,y) in enumerate(L) :
    C[p].append([y,i])

for p in range(N+1) :
    for i,(y,_) in enumerate(sorted(C[p])) :
        ans[_] = str(p).zfill(6) + str(i+1).zfill(6)
for i in range(M) :
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
L = []
ans = []
for i in range(M) :
    L.append(list(map(int,input().split())))
    ans.append([])

C = []
for i in range(N+1) :
    C.append([])

for i, (p,y) in enumerate(L) :
    C[p].append([y,i])

for p in range(N+1) :
    for i,(y,_) in enumerate(sorted(C[p])) :
        ans[_] = str(p).zfill(6) + str(i+1).zfill(6)
for i in range(N+1) :
    print(ans[i])


Fixed submission:
N,M = map(int,input().split())
L = []
ans = []
for i in range(M) :
    L.append(list(map(int,input().split())))
    ans.append([])

C = []
for i in range(N+1) :
    C.append([])

for i, (p,y) in enumerate(L) :
    C[p].append([y,i])

for p in range(N+1) :
    for i,(y,_) in enumerate(sorted(C[p])) :
        ans[_] = str(p).zfill(6) + str(i+1).zfill(6)
for i in range(M) :
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

N,M = map(int,input().split())
L = sorted(make_divisor_list(M),reverse = True)
for j in L :
    if j <= M//N :
        if (M - j*(N-1)) % j == 0 :
            print(j)
            break
            

Fixed submission:
import numpy as np
from math import sqrt
ANS = []
N,M = map(int,input().split())
L = np.arange(1,int(sqrt(M))+1,dtype=int)
#L = sorted(L,reverse = True)
for i in L :
    if M % i == 0 :
        ANS.append(i)
        ANS.append(M//i)
ANS = sorted(ANS,reverse = True)
for j in ANS :
    if j * N <= M :
        print(j)
        break

Buggy python submission (verdict: Runtime Error):
import numpy as np
N,M = map(int,input().split())
R = M//N+1
R = sorted(np.arange(R),reverse=True)
for i in R :
    if M % i == 0 :
        if (M-i*(N-1))%i == 0 :
            print(i)
            break


Fixed submission:
import numpy as np
from math import sqrt
ANS = []
N,M = map(int,input().split())
L = np.arange(1,int(sqrt(M))+1,dtype=int)
#L = sorted(L,reverse = True)
for i in L :
    if M % i == 0 :
        ANS.append(i)
        ANS.append(M//i)
ANS = sorted(ANS,reverse = True)
for j in ANS :
    if j * N <= M :
        print(j)
        break

Buggy python submission (verdict: Runtime Error):
import numpy as np
N,M = map(int,input().split())
R = M//N+1
R = sorted(np.arange(R),reverse=True)
for i in R :
    if (M-i*(N-1))%i == 0 :
        print(i)
        break


Fixed submission:
import numpy as np
from math import sqrt
ANS = []
N,M = map(int,input().split())
L = np.arange(1,int(sqrt(M))+1,dtype=int)
#L = sorted(L,reverse = True)
for i in L :
    if M % i == 0 :
        ANS.append(i)
        ANS.append(M//i)
ANS = sorted(ANS,reverse = True)
for j in ANS :
    if j * N <= M :
        print(j)
        break