Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
if k % 2 == 1:
    ans *= A.pop()
    ans %= p
    n -= 1
A = [A[i] * A[i + 1] for i in range(0, n, 2)]
A.sort(reverse=True)
for i in range(k // 2):
    ans *= A[i]
    ans %= p
print(ans)


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
# 全部0以下の場合かつkが奇数の場合はトップk個の積
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()

i = 0
j = n - 1
# kが奇数なら最大は絶対使う
if k % 2 == 1:
    ans *= A[j]
    ans %= p
    j -= 1
    k -= 1
    n -= 1
# 以下A[n-1]を除いてkを偶数として考える
k //= 2
for _ in range(min(k, n // 2)):
    # 2個ずつのペアを作って採用するかを決めていく
    left = A[i] * A[i + 1]
    right = A[j] * A[j - 1]
    if (left > right):
        ans *= left
        ans %= p
        i += 2
    else:
        ans *= right
        ans %= p
        j -= 2
print(ans)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
if k % 2 == 1:
    ans *= A.pop()
    ans %= p
A = [A[i] * A[i + 1] for i in range(0, n, 2)]
A.sort(reverse=True)
for i in range(k // 2):
    ans *= A[i]
    ans %= p
print(ans)


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
# 全部0以下の場合かつkが奇数の場合はトップk個の積
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()

i = 0
j = n - 1
# kが奇数なら最大は絶対使う
if k % 2 == 1:
    ans *= A[j]
    ans %= p
    j -= 1
    k -= 1
    n -= 1
# 以下A[n-1]を除いてkを偶数として考える
k //= 2
for _ in range(min(k, n // 2)):
    # 2個ずつのペアを作って採用するかを決めていく
    left = A[i] * A[i + 1]
    right = A[j] * A[j - 1]
    if (left > right):
        ans *= left
        ans %= p
        i += 2
    else:
        ans *= right
        ans %= p
        j -= 2
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
A.append(0)
B.append(0)
time = 0
cnt = 0
a, b = 0, 0
while (a < m and time + A[a] <= k) or (b < n and time + B[b] <= k):
    if (a < m and time + A[a] <= k) and (b < n and time + B[b] <= k):
        if A[a] <= B[b]:
            cnt += 1
            time += A[a]
            a += 1
        else:
            cnt += 1
            time += B[b]
            b += 1
    elif (a < m and time + A[a] <= k):
        cnt += 1
        time += A[a]
        a += 1
    else:
        cnt += 1
        time += B[b]
        b += 1
print(cnt)


Fixed submission:
n, m, k = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
SA, SB = [0], [0]
for i in range(n):
    SA.append(SA[i] + A[i])
for j in range(m):
    SB.append(SB[j] + B[j])
ans, tmp = 0, m
for i in range(n + 1):
    if SA[i] > k:
        break
    for j in range(tmp + 1)[::-1]:
        if SA[i] + SB[j] <= k:
            break
    ans = max(ans, i + j)
    tmp = j
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)


Fixed submission:
n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
n = len(input())
p = 10**9 + 7
fct, inv = [1], [1]
a, b = 1, 1
for i in range(1, n + k + 1):
    a = (a * i) % p
    b = (b * pow(i, p - 2, p)) % p
    fct.append(a)
    inv.append(b)
ans = 0
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow(25, i, p) * pow(26, k - i, p) * c
    ans %= p
print(ans)


Fixed submission:
k = int(input())
n = len(input())
p = 10**9 + 7
a = 1
fct = [a]
for i in range(1, n + k + 1):
    a = (a * i) % p
    fct.append(a)
b = pow(fct[-1], p - 2, p)
inv = [b]
for i in range(1, n + k + 1)[::-1]:
    b = (b * i) % p
    inv.append(b)
inv.reverse()
ans = 0
pow25, pow26 = [1], [1]
for i in range(1, k + 1):
    pow25.append((pow25[-1] * 25) % p)
    pow26.append((pow26[-1] * 26) % p)
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow25[i] * pow26[k - i] * c
    ans %= p
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
n = len(input())
p = 10**9 + 7
fct, inv = [1], [1]
a, b = 1, 1
for i in range(1, n + k + 1):
    a = (a * i) % p
    b = (b * pow(i, p - 2, p)) % p
    fct.append(a)
    inv.append(b)
ans = 0
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow(25, i, p) * pow(26, k - i, p) * c
    ans %= p
print(ans)


Fixed submission:
k = int(input())
n = len(input())
p = 10**9 + 7
a = 1
fct = [a]
for i in range(1, n + k + 1):
    a = (a * i) % p
    fct.append(a)
b = pow(fct[-1], p - 2, p)
inv = [b]
for i in range(1, n + k + 1)[::-1]:
    b = (b * i) % p
    inv.append(b)
inv.reverse()
ans = 0
pow25, pow26 = [1], [1]
for i in range(1, k + 1):
    pow25.append((pow25[-1] * 25) % p)
    pow26.append((pow26[-1] * 26) % p)
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow25[i] * pow26[k - i] * c
    ans %= p
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j >= A[i]:
            DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
        else:
            DP[i + 1][j] = (2 * DP[i][j]) % p
print(DP[n][s] % p)


Fixed submission:
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j >= A[i]:
            DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
        else:
            DP[i + 1][j] = (2 * DP[i][j]) % p
print(DP[n][s] % p)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(60)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 60):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(100)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 100):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(100)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 100):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
m = 60
DP = [[None for j in range(m)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, m):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


Fixed submission:
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, max(n, m) + 1):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a, b = n, 1
V = [False for d in range(1, m + 2)]
for i in range(m):
    d = min(a - b, n - (a - b))
    if 2 * d == n or V[d]:
        a -= 1
    print(a, b)
    d = min(a - b, n - (a - b))
    V[d] = True
    a -= 1
    b += 1


Fixed submission:
n, m = map(int, input().split())
a, b = n, 1
V = [False for d in range(1, n + 1)]
for i in range(m):
    d = min(a - b, n - (a - b))
    if 2 * d == n or V[d]:
        a -= 1
    print(a, b)
    d = min(a - b, n - (a - b))
    V[d] = True
    a -= 1
    b += 1
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
l = len(S)
T = [0]
for i in range(1, l+1):
    T.append((T[-1]+int(S[-i])*10**(i-1)) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)


Fixed submission:
S = [int(i) for i in list(input())]
S.reverse()
l = len(S)
T = [0]
for i in range(l):
    T.append((T[-1]+S[i]*(pow(10, i, 2019))) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
l = len(S)
T = [0]
for i in range(1, l+1):
    T.append((T[-1]+int(S[-i])*10**(i-1)) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)


Fixed submission:
S = [int(i) for i in list(input())]
S.reverse()
l = len(S)
T = [0]
for i in range(l):
    T.append((T[-1]+S[i]*(pow(10, i, 2019))) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [(None, None) for i in range(n)]
DP[0] = (0, A[0])
DP[1] = (0, max(A[0], A[1]))
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])


Fixed submission:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [[-inf]*2 for i in range(n)]
DP[0][0] = 0
DP[0][1] = A[0]
DP[1][0] = 0
DP[1][1] = max(A[0], A[1])
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])

Buggy python submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
inf = 10**18
X0 = (0, A[0])
X1 = (0, max(A[0], A[1]))
for i in range(2, n):
    X20 = max(X0[0]+A[i], X1[1]*(1-i % 2)+X1[0]*(i % 2))
    X21 = max(X0[1]+A[i], X1[1]*(1-i % 2)+(-inf)*(i % 2))
    X2 = (X20, X21)
    X0, X1 = X1, X2
if n % 2 == 1:
    print(X2[0])
else:
    print(X2[1])


Fixed submission:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [[-inf]*2 for i in range(n)]
DP[0][0] = 0
DP[0][1] = A[0]
DP[1][0] = 0
DP[1][1] = max(A[0], A[1])
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])
Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(s + 1):
        DP[i][j] += DP[i - 1][j]
        if j >= A[i - 1]:
            DP[i][j] += DP[i - 1][j - A[i - 1]]
        if j == A[i - 1] or j == 0:
            DP[i][j] += 1
        DP[i][j] %= p
ans = 0
for i in range(1, n + 1):
    ans += DP[i][s]
    ans %= p
print(ans)


Fixed submission:
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(s + 1):
        DP[i][j] += DP[i - 1][j]
        if j >= A[i - 1]:
            DP[i][j] += DP[i - 1][j - A[i - 1]]
        if j == A[i - 1] or j == 0:
            DP[i][j] += 1
        DP[i][j] %= p
ans = 0
for i in range(1, n + 1):
    ans += DP[i][s]
    ans %= p
print(ans)
Buggy python submission (verdict: Runtime Error):
n, d, a = map(int, input().split())
XH = [tuple(map(input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)


Fixed submission:
n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
# n, d, a = 9, 2, 2
# X = [1, 3, 4, 6, 9, 10, 12, 13, 16]
# H = [7, 6, 7, 5, 10, 3, 8, 9, 6]
X.append(10**10)
H.append(0)
j = 0
c = 0
S = [0]*(n+1)
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + -(-H[i]//a)*a
    S[j] -= -(-H[i]//a)*a
    # print(i)
    # print(H)
    # print(S)
# print(H)
# print(S)
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
def grid2graph(grid):
    # .が道で#が壁のグリッドをグラフに変換する
    H, W = len(grid), len(grid[0])
    f = {}
    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '.':
                f[(h, w)] = cnt
                cnt += 1
    G = [[] for i in range(cnt)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                continue
            i = f[(h, w)]
            if 0 <= h-1 and grid[h-1][w] == '.':
                j = f[(h-1, w)]
                G[i].append(j)
            if 0 <= w-1 and grid[h][w-1] == '.':
                j = f[(h, w-1)]
                G[i].append(j)
            if h+1 < H and grid[h+1][w] == '.':
                j = f[(h+1, w)]
                G[i].append(j)
            if w+1 < W and grid[h][w+1] == '.':
                j = f[(h, w+1)]
                G[i].append(j)
    return G


def warshall_floyd(G):
    inf = 10**18
    n = len(G)
    d = [[inf for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 0
        for j in G[i]:
            d[i][j] = 1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


H, W = map(int, input().split())
S = []
for h in range(H):
    S.append(list(input()))
G = grid2graph(S)
d = warshall_floyd(G)
n = len(d)
ans = 0
for i in range(n-1):
    for j in range(n):
        ans = max(ans, d[i][j])
print(ans)


Fixed submission:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
H, W = map(int, input().split())
S = []
for h in range(H):
    Sh = list(input())
    S.append(Sh)
G = [[0 for _ in range(H*W)] for _ in range(H*W)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            if h > 0 and S[h-1][w] == '.':
                G[h * W + w][(h - 1) * W + w] = 1
                G[(h - 1) * W + w][h * W + w] = 1
            if w > 0 and S[h][w-1] == '.':
                G[h * W + w][h * W + (w - 1)] = 1
                G[h * W + (w - 1)][h * W + w] = 1
            if h < H - 1 and S[h+1][w] == '.':
                G[h * W + w][(h + 1) * W + w] = 1
                G[(h + 1) * W + w][h * W + w] = 1
            if w < W - 1 and S[h][w+1] == '.':
                G[h * W + w][h * W + (w + 1)] = 1
                G[h * W + (w + 1)][h * W + w] = 1
graph = csr_matrix(G)
dist_matrix = floyd_warshall(csgraph=graph, directed=False)
max_dist = 0
for i in range(H * W):
    for j in range(H * W):
        d = dist_matrix[i][j]
        if d != np.inf and d > max_dist:
            max_dist = d
print(int(max_dist))
Buggy python submission (verdict: Runtime Error):
import functools
import math
def lcm(a, b):
    return a * b // math.gcd(a, b)
N,M=map(int,input().split())
A=list(map(int,input().split()))
LCM=functools.reduce(lcm,A)
HLCM=LCM//2
Y=M//HLCM
if Y%2==0:
    print(Y//2)
else:
    print((Y+1)//2)


Fixed submission:
import functools
import fractions

def lcm(a, b):
    return a * b // fractions.gcd(a, b)

# xが2で何回割れるか
def div2count(x):
    count=0
    while x%2==0:
        x=x//2
        count+=1
    return count

N,M=map(int,input().split())
A=list(map(int,input().split()))
if len(set(map(div2count,A)))!=1:
    print(0)
    exit()
LCM=functools.reduce(lcm,A)
HLCM=LCM//2
Y=M//HLCM
if Y%2==0:
    print(Y//2)
else:
    print((Y+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
*A, = map(int, input().split())
A.sort()

# Aの累積和を求めておく
S = [0]
x = 0
for a in A:
    x += a
    S.append(x)


def lower(x):
    # A[i]<xなるiの個数
    left = -1
    right = n
    while right-left > 1:
        mid = (left+right)//2
        if A[mid] < x:
            left = mid
        else:
            right = mid
    return right


def lower_pair(x):
    # A[i]+A[j]<xなる(i,j)の個数
    cnt = 0
    for a in A:
        cnt += lower(x-a)
    return cnt


# A[i]+A[j]のm番目に大きい値を求める
# lower_pair(x)<n**2-mなる最大のxを求めればよい
left = 2*min(A)
right = 2*max(A)
while right-left > 1:
    mid = (left+right)//2
    if lower_pair(mid) < n**2-m:
        left = mid
    else:
        right = mid
x = left

# A[i]+A[j]>=xとなる(i,j)の個数とA[i]+A[j]の総和を求める
k = n**2-lower_pair(x)
s = 0
for a in A:
    cnt = lower(x-a)
    s += (n-cnt)*a+S[n]-S[cnt]

print(s-(k-m)*x)


Fixed submission:
n, m = map(int, input().split())
*A, = map(int, input().split())
A.sort()

# Aの累積和を求めておく
S = [0]
x = 0
for a in A:
    x += a
    S.append(x)


def lower(x):
    # A[i]<xなるiの個数
    left = -1
    right = n
    while right-left > 1:
        mid = (left+right)//2
        if A[mid] < x:
            left = mid
        else:
            right = mid
    return right


def lower_pair(x):
    # A[i]+A[j]<xなる(i,j)の個数
    cnt = 0
    for a in A:
        cnt += lower(x-a)
    return cnt


# A[i]+A[j]のm番目に大きい値を求める
# lower_pair(x)<n**2-mなる最大のxを求めればよい
left = 2*min(A)
right = 2*max(A)
while right-left > 1:
    mid = (left+right)//2
    if lower_pair(mid) < n**2-m:
        left = mid
    else:
        right = mid
x = left

# A[i]+A[j]>=xとなる(i,j)の個数とA[i]+A[j]の総和を求める
k = n**2-lower_pair(x)
s = 0
for a in A:
    cnt = lower(x-a)
    s += (n-cnt)*a+S[n]-S[cnt]

print(s-(k-m)*x)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)


Fixed submission:
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]:
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)