Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7


def solve(k, s):
    res = 0
    factorial = [1] * (2 * 10 ** 6)
    factorial_inv = [1] * (2 * 10 ** 6)
    for i in range(1, 2 * 10 ** 6):
        factorial[i] = factorial[i - 1] * i % MOD
    factorial_inv[-1] = pow(factorial[-1], MOD - 2, MOD)
    for i in range(2 * 10 ** 6 - 1, 0, -1):
        factorial_inv[i - 1] = factorial_inv[i] * i % MOD
    # print(factorial[:5])
    # print(factorial_inv[:5])
    for i in range(k + 1):
        left = k - i + len(s) - 1
        right = len(s) - 1
        ncr = (factorial[left] * factorial_inv[right] * factorial_inv[left - right]) % MOD
        add = (ncr * pow(25, k - i, MOD) * pow(26, i, MOD)) % MOD
        res += add
        res %= MOD
    # print(res)
    return res


def main():
    k = int(input())
    s = input()
    res = solve(k, s)
    print(res)


def test():
    assert solve(1, "abc") == 25 + 25 + 25 + 26
    assert solve(5, "oof") == 575111451
    assert solve(37564, "whydidyoudesertme") == 318008117


if __name__ == "__main__":
    test()
    main()


Fixed submission:
MOD = 10 ** 9 + 7


def solve(k, s):
    res = 0
    factorial = [1] * (2 * 10 ** 6)
    factorial_inv = [1] * (2 * 10 ** 6)
    for i in range(1, 2 * 10 ** 6):
        factorial[i] = factorial[i - 1] * i % MOD
    factorial_inv[-1] = pow(factorial[-1], MOD - 2, MOD)
    for i in range(2 * 10 ** 6 - 1, 0, -1):
        factorial_inv[i - 1] = factorial_inv[i] * i % MOD
    # print(factorial[:5])
    # print(factorial_inv[:5])
    for i in range(k + 1):
        left = k - i + len(s) - 1
        right = len(s) - 1
        ncr = (factorial[left] * factorial_inv[right] * factorial_inv[left - right]) % MOD
        add = (ncr * pow(25, k - i, MOD) * pow(26, i, MOD)) % MOD
        res += add
        res %= MOD
    # print(res)
    return res


def main():
    k = int(input())
    s = input()
    res = solve(k, s)
    print(res)


def test():
    assert solve(1, "abc") == 25 + 25 + 25 + 26
    assert solve(5, "oof") == 575111451
    assert solve(37564, "whydidyoudesertme") == 318008117


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Runtime Error):
def solve(n, a_list, s):

    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            r = 2 ** (a_list[i].bit_length() - 1)
            for j in range(i):
                if a_list[j] & r > 0:
                    a_list[j] = a_list[i] ^ a_list[j]
        else:
            if a_list[i] > 0:
                return 1
    return 0


def main():
    t = int(input())
    res_list = []
    for _ in range(t):
        n = int(input())
        a_list = list(map(int, input().split()))
        s = input()
        res = solve(n, a_list, s)
        res_list.append(res)
    for res in res_list:
        print(res)


def test():
    assert solve(2, [1, 2], "10") == 1
    assert solve(2, [1, 1], "10") == 0
    assert solve(6, [2, 3, 4, 5, 6, 7], "111000") == 0


if __name__ == "__main__":
    test()
    main()


Fixed submission:
def solve(n, a_list, s):

    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            if a_list[i] == 0:
                continue
            r = 2 ** (a_list[i].bit_length() - 1)
            for j in range(i):
                if a_list[j] & r > 0:
                    a_list[j] = a_list[i] ^ a_list[j]
        else:
            if a_list[i] > 0:
                return 1
    return 0


def main():
    t = int(input())
    res_list = []
    for _ in range(t):
        n = int(input())
        a_list = list(map(int, input().split()))
        s = input()
        res = solve(n, a_list, s)
        res_list.append(res)
    for res in res_list:
        print(res)


def test():
    assert solve(2, [1, 2], "10") == 1
    assert solve(2, [1, 1], "10") == 0
    assert solve(6, [2, 3, 4, 5, 6, 7], "111000") == 0


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353


def solve(n, s, a_list):
    dp = [[0] * 3001 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        a = a_list[i]
        for v in range(3001):
            dp[i + 1][v] = (dp[i][v] * 2) % MOD
        for v in range(3001):
            if v + a > 3000:
                break
            dp[i + 1][v + a] = (dp[i + 1][v + a] + dp[i][v]) % MOD
    # print(dp[n])
    return dp[n][s]


def main():
    n, s = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, s, a_list)
    print(res)


def test():
    assert solve(3, 4, [2, 2, 4]) == 6
    assert solve(5, 8, [9, 9, 9, 9, 9]) == 0
    assert solve(10, 10, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]) == 3296


if __name__ == "__main__":
    test()
    main()


Fixed submission:
MOD = 998244353


def solve(n, s, a_list):
    dp = [[0] * 3001 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        a = a_list[i]
        for v in range(3001):
            dp[i + 1][v] = (dp[i][v] * 2) % MOD
        for v in range(3001):
            if v + a > 3000:
                break
            dp[i + 1][v + a] = (dp[i + 1][v + a] + dp[i][v]) % MOD
    # print(dp[n])
    return dp[n][s]


def main():
    n, s = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, s, a_list)
    print(res)


def test():
    assert solve(3, 4, [2, 2, 4]) == 6
    assert solve(5, 8, [9, 9, 9, 9, 9]) == 0
    assert solve(10, 10, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]) == 3296


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def solve(s):
    dp = [0] * 2019
    dp[0] = 1
    r = 0
    for i in range(1, len(s) + 1):
        r += int(s[-i]) * (10 ** (i - 1))
        r %= 2019
        dp[r] += 1
    res = 0
    for r in range(2019):
        res += dp[r] * (dp[r] - 1) // 2
    return res


def main():
    s = input()
    res = solve(s)
    print(res)


def test():
    assert solve("1817181712114") == 3
    assert solve("14282668646") == 2
    assert solve("2119") == 0


if __name__ == "__main__":
    test()
    main()


Fixed submission:
def solve(s):
    dp = [0] * 2019
    dp[0] = 1
    r = 0
    for i in range(1, len(s) + 1):
        r += int(s[-i]) * pow(10, i - 1, 2019)
        r %= 2019
        dp[r] += 1
    res = 0
    for r in range(2019):
        res += dp[r] * (dp[r] - 1) // 2
    return res


def main():
    s = input()
    res = solve(s)
    print(res)


def test():
    assert solve("1817181712114") == 3
    assert solve("14282668646") == 2
    assert solve("2119") == 0


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        for j in range(n):
            dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        # dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, -1 - i, -1)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()


Fixed submission:
from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        # for j in range(n):
        #    dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, n + n - 1 - i)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Runtime Error):
def solve(n, s):

    r_list = [i for i in range(n) if s[i] == "R"]
    g_list = [i for i in range(n) if s[i] == "G"]
    # b_list = [i for i in range(n) if s[i] == "B"]
    b_dict = {i: 1 for i in range(n) if s[i] == "B"}

    res = len(r_list) * len(g_list) * len(b_list)
    for i in r_list:
        for j in g_list:
            # candidate
            m, n = min(i, j), max(i, j)
            if n + (n - m) in b_dict.keys():
                res -= 1
            if m - (n - m) in b_dict.keys():
                res -= 1
            if (n - m) % 2 == 0 and (n + m) // 2 in b_dict.keys():
                res -= 1

    return res


def main():
    n = int(input())
    s = input()
    res = solve(n, s)
    print(res)


def test():
    assert solve(4, "RRGB") == 1
    assert solve(39, "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB") == 1800


if __name__ == "__main__":
    test()
    main()


Fixed submission:
def solve(n, s):

    r_list = [i for i in range(n) if s[i] == "R"]
    g_list = [i for i in range(n) if s[i] == "G"]
    # b_list = [i for i in range(n) if s[i] == "B"]
    b_dict = {i: 1 for i in range(n) if s[i] == "B"}

    res = len(r_list) * len(g_list) * len(b_dict.keys())
    for i in r_list:
        for j in g_list:
            # candidate
            m, n = min(i, j), max(i, j)
            if n + (n - m) in b_dict.keys():
                res -= 1
            if m - (n - m) in b_dict.keys():
                res -= 1
            if (n - m) % 2 == 0 and (n + m) // 2 in b_dict.keys():
                res -= 1

    return res


def main():
    n = int(input())
    s = input()
    res = solve(n, s)
    print(res)


def test():
    assert solve(4, "RRGB") == 1
    assert solve(39, "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB") == 1800


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def solve(n, t, ab_list):
    a0b_list = [ab[1] for ab in ab_list if ab[0] == 0]
    apb_list = [ab for ab in ab_list if ab[0] > 0]
    a0b_list = sorted(a0b_list)
    apb_list = sorted(apb_list, key=lambda x: - x[0] / (x[1] + 1))
    # DP
    m = len(apb_list)
    dp = [[t + 1] * 30 for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 0
    for i in range(m):
        for k in range(1, 30):
            ti = dp[i][k - 1] + 1
            a, b = apb_list[i]
            dp[i + 1][k] = min(dp[i][k], ti + a * ti + b)
    a0b_list_cum_sum = [0]
    s = 0
    for b in a0b_list:
        s += b + 1
        a0b_list_cum_sum.append(s)

    res = 0

    for k in range(len(a0b_list_cum_sum)):
        for p in range(30):
            if dp[m][p] + a0b_list_cum_sum[k] <= t:
                res = max(res, k + p)
                
    return res


def main():
    n, t = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(3, 7, [[2, 0], [3, 2], [0, 3]]) == 2
    assert solve(1, 3, [[0, 3]]) == 0
    assert solve(5, 21600, [[2, 14], [3, 22], [1, 3], [1, 10], [1, 9]]) == 5


if __name__ == "__main__":
    test()
    main()


Fixed submission:
def solve(n, t, ab_list):
    a0b_list = [ab[1] for ab in ab_list if ab[0] == 0]
    apb_list = [ab for ab in ab_list if ab[0] > 0]
    a0b_list = sorted(a0b_list)
    apb_list = sorted(apb_list, key=lambda x: - x[0] / (x[1] + 1))
    # DP
    m = len(apb_list)
    dp = [[t + 1] * 30 for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 0
    for i in range(m):
        for k in range(1, 30):
            ti = dp[i][k - 1] + 1
            a, b = apb_list[i]
            dp[i + 1][k] = min(dp[i][k], ti + a * ti + b)
    a0b_list_cum_sum = [0]
    s = 0
    for b in a0b_list:
        s += b + 1
        a0b_list_cum_sum.append(s)

    res = 0

    for k in range(len(a0b_list_cum_sum)):
        for p in range(30):
            if dp[m][p] + a0b_list_cum_sum[k] <= t:
                res = max(res, k + p)

    return res


def main():
    n, t = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(3, 7, [[2, 0], [3, 2], [0, 3]]) == 2
    assert solve(1, 3, [[0, 3]]) == 0
    assert solve(5, 21600, [[2, 14], [3, 22], [1, 3], [1, 10], [1, 9]]) == 5


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
LARGE = 10 ** 9 + 7


def solve(n, a, b):

    pow_ab = [1] * (b + 1)
    for i in range(b):
        pow_ab[i + 1] = pow_ab[i] * (i + 1)
    pow_ab_inv = [1] * (b + 1)
    pow_ab_inv[-1] = pow(pow_ab[-1], LARGE - 2, LARGE)
    for i in range(b - 1, 0, -1):
        pow_ab_inv[i] = pow_ab_inv[i + 1] * (i + 1) % LARGE

    res_all = pow(2, n, LARGE) - 1
    res_ab = 1
    for i in range(a):
        res_ab *= (n - i)
    res_all -= res_ab * pow_ab_inv[a]
    for i in range(a, b):
        res_ab *= (n - i)
    res_all -= res_ab * pow_ab_inv[b]
    return res_all % LARGE


def main():
    n, a, b = map(int, input().split())
    res = solve(n, a, b)
    print(res)


def test():
    assert solve(4, 1, 3) == 7
    assert solve(1000000000, 141421, 173205) == 34076506


if __name__ == "__main__":
    test()
    main()


Fixed submission:
LARGE = 10 ** 9 + 7


def solve(n, a, b):

    pow_ab = [1] * (b + 1)
    for i in range(b):
        pow_ab[i + 1] = pow_ab[i] * (i + 1) % LARGE
    pow_ab_inv = [1] * (b + 1)
    pow_ab_inv[-1] = pow(pow_ab[-1], LARGE - 2, LARGE)
    for i in range(b - 1, 0, -1):
        pow_ab_inv[i] = pow_ab_inv[i + 1] * (i + 1) % LARGE

    res_all = pow(2, n, LARGE) - 1
    res_ab = 1
    for i in range(a):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[a]
    for i in range(a, b):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[b]
    return res_all % LARGE


def main():
    n, a, b = map(int, input().split())
    res = solve(n, a, b)
    print(res)


def test():
    assert solve(4, 1, 3) == 7
    assert solve(1000000000, 141421, 173205) == 34076506


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Runtime Error):
import sys


TEST_INPUT = [
    """
    red blue
    3 4
    red
    """,
    """
    red blue
    5 5
    blue
    """
]
ANSWER = [
    "2 4",
    "5 4"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def solve(s, t, a, b, u):
    if s == u:
        return f"{a - 1} {b}"
    else:
        return f"{a} {b - 1}"


def main():
    ih = InputHandler()
    s, t = ih.input().split()
    a, b = map(int, ih.input().split())
    u = ih.input()
    res = solve(s, t, a, b, u)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        s, t = ih.input().split()
        a, b = map(int, ih.input().split())
        u = ih.input()
        res = solve(s, t, a, b, u)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()


Fixed submission:
import sys


TEST_INPUT = [
    """
    red blue
    3 4
    red
    """,
    """
    red blue
    5 5
    blue
    """
]
ANSWER = [
    "2 4",
    "5 4"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def solve(s, t, a, b, u):
    if s == u:
        return str(a - 1) + " " + str(b)
    else:
        return str(a) + " " + str(b - 1)


def input_and_solve(ih):
    s, t = ih.input().split()
    a, b = map(int, ih.input().split())
    u = ih.input()
    res = solve(s, t, a, b, u)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

LARGE = 10 ** 9 + 7


def solve(n, a_list):

    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE

    # primes
    p_candidate_arr = np.ones(10 ** 3, dtype=np.int)
    p_candidate_arr[:2] = 0
    for p in range(2, 10 ** 3):
        if p_candidate_arr[p]:
            p_candidate_arr[p * p::p] = 0
    primes_1000 = np.where(p_candidate_arr == 1)[0]

    lcm = 1
    for p in primes_1000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE

    for q in np.unique(a_list):
        lcm *= q
        lcm %= LARGE

    return res * lcm % LARGE


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(3, [2, 3, 4]) == 13
    assert solve(5, [12, 12, 12, 12, 12]) == 5
    assert solve(3, [1000000, 999999, 999998]) == 996989508


if __name__ == "__main__":
    test()
    main()


Fixed submission:
LARGE = 10 ** 9 + 7


def solve(n, a_list):

    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE

    # primes
    p_candidate_list = [1] * 10 ** 3
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 3):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 3, p):
                p_candidate_list[q] = 0
    primes_1000 = [p for p in range(1000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE

    for q in set(a_list):
        lcm *= q
        lcm %= LARGE

    return res * lcm % LARGE


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(3, [2, 3, 4]) == 13
    assert solve(5, [12, 12, 12, 12, 12]) == 5
    assert solve(3, [1000000, 999999, 999998]) == 996989508


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
LARGE = 10 ** 9 + 7


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    z = (x + y) // 3
    if x < z or y < z:
        return 0
    # zC(x-z)
    r = min(x - z, y - z)
    res = 1
    for i in range(r):
        res *= z - i
        res *= pow(i + 1, LARGE - 2, LARGE)
        res %= LARGE
    return res


def main():
    x, y = map(int, input().split())
    res = solve(x, y)
    print(res)


def test():
    assert solve(3, 3) == 2
    assert solve(2, 2) == 0
    assert solve(999999, 999999) == 151840682


if __name__ == "__main__":
    test()
    main()


Fixed submission:
LARGE = 10 ** 9 + 7


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    z = (x + y) // 3
    if x < z or y < z:
        return 0
    # zC(x-z)
    r = min(x - z, y - z)
    res = 1
    for i in range(r):
        res *= z - i
        res *= pow(i + 1, LARGE - 2, LARGE)
        res %= LARGE
    return res


def main():
    x, y = map(int, input().split())
    res = solve(x, y)
    print(res)


def test():
    assert solve(3, 3) == 2
    assert solve(2, 2) == 0
    assert solve(999999, 999999) == 151840682


if __name__ == "__main__":
    # test()
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def solve(n, t, ab_list):
    ab_list_s = sorted(ab_list, key=lambda x: x[0])
    res = 0
    dp = [0] * t
    for i in range(n):
        for s in range(t - 1, -1, -1):
            if dp[s] > 0 or s == 0:
                u = s + ab_list_s[i][0]
                r = dp[s] + ab_list_s[i][1]
                if u >= t:
                    res = max(res, r)
                else:
                    dp[u] = max(dp[u], r)
    return max(res, max(dp))


def main():
    n, t = map(int, input().split())
    ab_list = []
    for _ in range(n):
        a, b = map(int, input().split())
        ab_list.append([a, b])
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(2, 60, [[10, 10], [100, 100]]) == 110
    assert solve(3, 60, [[10, 10], [10, 20], [10, 30]]) == 60
    assert solve(3, 60, [[30, 10], [30, 20], [30, 30]]) == 50


if __name__ == "__main__":
    test()
    main()


Fixed submission:
def solve(n, t, ab_list):
    ab_list_s = sorted(ab_list, key=lambda x: x[0])
    res = 0
    dp = [0] * t
    for i in range(n):
        for s in range(t - 1, -1, -1):
            if dp[s] > 0 or s == 0:
                u = s + ab_list_s[i][0]
                r = dp[s] + ab_list_s[i][1]
                if u >= t:
                    res = max(res, r)
                else:
                    dp[u] = max(dp[u], r)
    return max(res, max(dp))


def main():
    n, t = map(int, input().split())
    ab_list = []
    for _ in range(n):
        a, b = map(int, input().split())
        ab_list.append([a, b])
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(2, 60, [[10, 10], [100, 100]]) == 110
    assert solve(3, 60, [[10, 10], [10, 20], [10, 30]]) == 60
    assert solve(3, 60, [[30, 10], [30, 20], [30, 30]]) == 50


if __name__ == "__main__":
    # test()
    main()
Buggy python submission (verdict: Runtime Error):
LARGE = 998244353


def solve(n, d_list):
    cnt = [0] * (max(d_list) + 1)
    for i in range(n):
        cnt[d_list[i]] += 1
    if cnt[0] != 1 or d_list[0] != 0:
        return 0
    res = 1
    for i in range(max(d_list)):
        res *= pow(cnt[i], cnt[i + 1], LARGE)
        res %= LARGE
    return res


def main():
    n = int(input())
    d_list = list(map(int(input())))
    res = solve(n, d_list)
    print(res)


def test():
    assert solve(4, [0, 1, 1, 2]) == 2
    assert solve(4, [1, 1, 1, 1]) == 0
    assert solve(7, [0, 3, 2, 1, 2, 2, 1]) == 24


if __name__ == "__main__":
    test()
    main()


Fixed submission:
LARGE = 998244353


def solve(n, d_list):
    cnt = [0] * (max(d_list) + 1)
    for i in range(n):
        cnt[d_list[i]] += 1
    if cnt[0] != 1 or d_list[0] != 0:
        return 0
    res = 1
    for i in range(max(d_list)):
        res *= pow(cnt[i], cnt[i + 1], LARGE)
        res %= LARGE
    return res


def main():
    n = int(input())
    d_list = list(map(int, input().split()))
    res = solve(n, d_list)
    print(res)


def test():
    assert solve(4, [0, 1, 1, 2]) == 2
    assert solve(4, [1, 1, 1, 1]) == 0
    assert solve(7, [0, 3, 2, 1, 2, 2, 1]) == 24


if __name__ == "__main__":
    test()
    main()