Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)

cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp

Fixed submission:
K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)
    exit()


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)

cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp




Fixed submission:
K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)
    exit()


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp
Buggy python submission (verdict: Time Limit Exceeded):
H = int(input())

count = 0
while True:
    count += 1
    H = H // 2
    if H == 1:
        break

L = 2 ** (count + 1) - 1

print(L)

Fixed submission:
H = int(input())
import numpy as np
from math import ceil

L = int(np.log2(H))
K = ceil(np.log2(H))
if K == L:
    count = K
else:
    count = K - 1
L = 2 ** (count + 1) - 1

print(L)

Buggy python submission (verdict: Time Limit Exceeded):
H = int(input())

count = 0
number = 1
while True:
    H = H // 2
    number *= 2
    if H == 1:
        count += number + 1
        break
    else:
        count += number

print(count)

Fixed submission:
H = int(input())
import numpy as np
from math import ceil

L = int(np.log2(H))
K = ceil(np.log2(H))
if K == L:
    count = K
else:
    count = K - 1
L = 2 ** (count + 1) - 1

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

count = 1

for i in range(1, len(P)):
    if min(P[:i]) >= P[i]:
        count += 1

print(count)

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

count = 1
m = P[0]
for i in range(1, len(P)):
    m = min(m, P[i - 1])
    if m >= P[i]:
        count += 1

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
count = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if str(i)[0] == str(j)[-1] and str(i)[-1] == str(j)[0]:
            count += 1
print(count)

Fixed submission:
N = int(input())
d = dict()
for i in range(1, 10):
    for j in range(1, 10):
        d[str(i) + str(j)] = 0

for i in range(1, N + 1):
    if str(i)[-1] != '0':
        d[str(i)[0] + str(i)[-1]] += 1

result = 0
for i in range(1, 10):
    for j in range(1, 10):
        result += d[str(i) + str(j)] * d[str(j) + str(i)]

print(result)
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // math.gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

print(result % (10 ** 9 + 7))

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

print(result % (10 ** 9 + 7))

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // math.gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

print(result % (10 ** 9 + 7))

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

print(result % (10 ** 9 + 7))
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())

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

print(lcm(A, B))

Fixed submission:
import fractions
A, B = map(int, input().split())

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

print(lcm(A, B))
Buggy python submission (verdict: Runtime Error):
import math

A, B, X = map(int, input().split())

# Nがとりうる最大値
L_M = X // A

if L_M < 1:
    print(0)
    exit()

if L_M >= 1 and (X - (int(math.log10(L_M)) + 1) * B) // A > 10 ** 9:
    print(10 ** 9)
    exit()

if L_M >= 1:
    while True:
        if A * L_M + B * (int(math.log10(L_M)) + 1) <= X:
            if L_M > 10 ** 9:
                print(10 ** 9)
            else:
                print(L_M)
            exit()
        elif L_M <= 0:
            print(0)
            exit()
        else:
            L_M -= 1
else:
    print(0)

Fixed submission:
S = input()
if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
elif S == "SAT":
    print(1)
Buggy python submission (verdict: Runtime Error):
import math

N = 10 ** 9 + 7

X, Y = map(int, input().split())

B3 = 2 * X - Y

if B3 % 3:
    print(0)
    exit()

B = B3 // 3

A = X - 2 * B

print(A)
print(B)


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

print(combinations_count(A + B, A) % N)


Fixed submission:
import math

N = 10 ** 9 + 7
X, Y = map(int, input().split())
B3 = 2 * X - Y
if B3 % 3:
    print(0)
    exit()
B = B3 // 3
A = X - 2 * B
if A < 0 or B < 0:
    print(0)
    exit()

# count = 1
# for i in range(A + 1, A + B + 1):
#     count *= i
# for i in range(1, A + 1):
#     count //= i
# print(count % N)

# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#
# print(combinations_count(A + B, A) % N)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(cmb(A + B,A) % N)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
k = max(A)

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

if A[0] != 0 or R[0] != 1:
    print(0)
    exit()

for j in range(k + 1):
    result *= pow_k(R[j], R[j + 1])

    if result == 0:
        print(0)
        exit()

print(result % 998244353)


Fixed submission:
N = int(input())

if N % 2 == 0:
    print(N // 2 - 1)
else:
    print((N + 1) // 2 - 1)

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
A = [int(a) for a in input().split()]

if A[0] != 0:
    print(0)
    exit()
if A.count(0) != 1:
    print(0)
    exit()

k = max(A)

R = [1]
result = 1


for i in range(k):
    R.append(A.count(i + 1))

for j in range(k):
    if R[j + 1] % 2 == 0:
        result *= (R[j] ** 2) ** (R[j + 1] // 2)
    else:
        result *= R[j] * (R[j] ** 2) ** (R[j + 1] // 2)
    result %= 998244353

    if result == 0:
        print(0)
        exit()

print(result)


Fixed submission:
N = int(input())

if N % 2 == 0:
    print(N // 2 - 1)
else:
    print((N + 1) // 2 - 1)
Buggy python submission (verdict: Runtime Error):
N = int(input())

import math

A = int(math.sqrt(N))

for i in reversed(range(A)):
    if N % i == 0:
        print(i + (N // i) - 2)
        exit()

Fixed submission:
import math

N = int(input())

A = int(math.sqrt(N))

for i in reversed(range(1, A + 1)):
    if N % i == 0:
        print(i + (N // i) - 2)
        exit()
Buggy python submission (verdict: Runtime Error):
import collections
import math
a, b = input().split()
A = int(a)
B = int(b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


GCB = math.gcd(A, B)

C = collections.Counter(prime_factorize(GCB))

print(len(C) + 1)



Fixed submission:
import collections
import fractions
a, b = input().split()
A = int(a)
B = int(b)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


GCB = fractions.gcd(A, B)

C = collections.Counter(prime_factorize(GCB))

print(len(C) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = []
for i in range(Q):
    Q_list.append(int(input()))

for i in range(N):
    p = K - (Q - Q_list.count(i + 1))
    if p <= 0:
        print("No")
    else:
        print("Yes")

Fixed submission:
n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = [0] * N
for i in range(Q):
    num = int(input())
    Q_list[num - 1] += 1

for i in range(N):
    p = K - (Q - Q_list[i])
    if p <= 0:
        print("No")
    else:
        print("Yes")

Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = []
for i in range(Q):
    Q_list.append(int(input()))

for i in range(N):
    p = K - len([a for a in Q_list if not a == i + 1])
    if p <= 0:
        print("No")
    else:
        print("Yes")

Fixed submission:
n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = [0] * N
for i in range(Q):
    num = int(input())
    Q_list[num - 1] += 1

for i in range(N):
    p = K - (Q - Q_list[i])
    if p <= 0:
        print("No")
    else:
        print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    a = copy.deepcopy(A)
    a.remove(A[i])
    print(max(a))


Fixed submission:
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    # rem = A[i]
    # A.remove(rem)
    # print(max(A))
    # A.insert(i, rem)
    ans = 0
    for j in range(N):
        if not i == j and ans < A[i]:
            ans = A[j]

    print(ans)



Fixed submission:
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    rem = A[i]
    A.remove(rem)
    print(max(A))
    A.insert(i, rem)


Fixed submission:
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list()
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    rem = A[i]
    A.remove(rem)
    print(max(A))
    A.insert(i, rem)


Fixed submission:
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)
Buggy python submission (verdict: Runtime Error):
"""
    Author : thekushalghosh
    Team   : CodeDiggers
"""
import sys,math,cmath,time
start_time = time.time()
################# ---- USER DEFINED INPUT FUNCTIONS ---- #################
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().split()))
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
 
def solve():
  n = inp()
  if "7" in list(str(n)):
    print("YES")
  else:
    print("NO")
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
ONLINE_JUDGE = __debug__
if not ONLINE_JUDGE:
    sys.stdin = open('input.txt','r')
    sys.stdout = open('output.txt','w')
else:
    input = sys.stdin.readline
t = 1
t = inp()
for tt in range(t):
    solve()
if not ONLINE_JUDGE:
    print("Time Elapsed:",time.time() - start_time,"seconds")
sys.stdout.close()

Fixed submission:
"""
    Author : thekushalghosh
    Team   : CodeDiggers
"""
import sys,math,cmath,time
start_time = time.time()
################# ---- USER DEFINED INPUT FUNCTIONS ---- #################
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().split()))
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
 
def solve():
  n = inp()
  if "7" in list(str(n)):
    print("Yes")
  else:
    print("No")
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
ONLINE_JUDGE = __debug__
if not ONLINE_JUDGE:
    sys.stdin = open('input.txt','r')
    sys.stdout = open('output.txt','w')
else:
    input = sys.stdin.readline
t = 1
for tt in range(t):
    solve()
if not ONLINE_JUDGE:
    print("Time Elapsed:",time.time() - start_time,"seconds")
sys.stdout.close()
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if int((N-1)**(1/2)) == (N-1)**(1/2):
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and N**(1/m) == int(N**(1/m)):###m=1のときはK=Nの話なのでpass
        Klist[int(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist)
###
print(sum(Klist)+count-Klist[1])


Fixed submission:
###草

import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if  (N-1)**(1/2) - int((N-1)**(1/2)) < 1e-10 or 1 + int((N-1)**(1/2)) - ((N-1)**(1/2)) < 1e-10:
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and (N**(1/m) - int(N**(1/m)) < 1e-10 or 1+int(N**(1/m))-N**(1/m) < 1e-10):###m=1のときはK=Nの話なのでpass
        Klist[round(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist[:100])
###
print(sum(Klist)+count-Klist[1])
Buggy python submission (verdict: Runtime Error):
N = list(map(int,list(input())))
K = int(input())
#print(N)

def main(k,p):
    l = len(k)
    x = 9 ** p###先頭桁が0
    for i in range(p):
        x *= max(l - 1 - i,0)
    for i in range(p):
        x //= (i+1)
    y = (k[0] - 1)*(9**(p-1))###先頭桁が1以上k[0]-1以下
    for i in range(p-1):
        y *= max(l - 1 - i,0)
    for i in range(p-1):
        y //= (i+1)
    ##以下, 先頭がk[0]
    i = 1
    while i < l-1 and k[i] == 0 :
        i += 1
    #print("i=",i)
    if p == 1:
        z = 1
    elif i == l-1 and k[i]==0:
        z = 0
    else:
        z = main(k[i:],p-1)
    #print(k,x,y,z)
    return (x+y)+z

print(main(N,K))

Fixed submission:
N = list(map(int,list(input())))
K = int(input())
#print(N)

def main(k,p):
    l = len(k)
    x = 9 ** p###先頭桁が0
    for i in range(p):
        x *= max(l - 1 - i,0)
    for i in range(p):
        x //= (i+1)
    y = (k[0] - 1)*(9**(p-1))###先頭桁が1以上k[0]-1以下
    for i in range(p-1):
        y *= max(l - 1 - i,0)
    for i in range(p-1):
        y //= (i+1)
    ##以下, 先頭がk[0]
    i = 1
    while i < l-1 and k[i] == 0 :
        i += 1
    #print("i=",i)
    if p == 1:
        z = 1
    elif i == l-1 and k[i]==0:
        z = 0
    else:
        z = main(k[i:],p-1)
    #print(k,x,y,z)
    return (x+y)+z

if len(N) < K:
    print(0)
else:
    print(main(N,K))
Buggy python submission (verdict: Time Limit Exceeded):
H,N = map(int,input().split())

data = []

for i in range(N):
  A,B = map(int,input().split())
  data.append([A,B])

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    #print(dp)
print(dp[H])

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

data = []

for i in range(N):
  A,B = map(int,input().split())
  data.append([A,B])

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    #print(dp)
print(dp[H])
Buggy python submission (verdict: Runtime Error):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


N_,K = map(int,input().split())

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

A.sort()

ans = 0

for i in range(K-1,N_):
    ans += cmb(i,K-1,mod) * A[i]
    ans %= mod
    #print(ans)

for i in range(K-1,N_):
    ans -= cmb(i,K-1,mod) * A[N_-i-1]
    ans %= mod
    #print(ans)

print(ans)

Fixed submission:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


N_,K = map(int,input().split())

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

A.sort()

ans = 0

for i in range(K-1,N_):
    ans += cmb(i,K-1,mod) * A[i]
    ans %= mod
    #print(ans)

for i in range(K-1,N_):
    ans -= cmb(i,K-1,mod) * A[N_-i-1]
    ans %= mod
    #print(ans)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def tentwo(N):
    ret = [0] * 60
    NN = N
    for i in range(60):
        ret[i] = NN % 2
        NN //= 2
    return ret

N = int(input())

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

B = [0] * N

for i in range(N):
    B[i] = tentwo(A[i])

ans = 0
for j in range(60):
    count = 0
    for i in range(N):
        if B[i][j] == 1:
            count += 1
    ans = (ans + (count * (N-count)) * (2 ** j)) % (10**9 + 7)

print(ans)

Fixed submission:
def tentwo(N):
    ret = [0] * 60
    NN = N
    for i in range(60):
        ret[i] = NN % 2
        NN //= 2
    return ret

N = int(input())

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

B = [0] * N

for i in range(N):
    B[i] = tentwo(A[i])

ans = 0
for j in range(60):
    count = 0
    for i in range(N):
        if B[i][j] == 1:
            count += 1
    ans = (ans + (count * (N-count)) * (2 ** j)) % (10**9 + 7)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int,input().split())
data = [0] * N

M = 0
for i in range(N):
    data[i] = list(map(int,input().split()))
    M = max(M,data[i][0])

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

for j in range(T):
    if j < data[0][0]:
        dp1[0][j] = 0
    else:
        dp1[0][j] = data[0][1]

for j in range(T):
    for i in range(1,N):
        if data[i][0] <= j:
            dp1[i][j] = max(dp1[i-1][j],dp1[i-1][j-data[i][0]]+data[i][1])
        else:
            dp1[i][j] = dp1[i-1][j]

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

for j in range(T):
    if j < data[N-1][0]:
        dp2[N-i][j] = 0
    else:
        dp2[N-1][j] = data[N-1][1]

for j in range(T):
    for i in range(N-2,-1,-1):
        if data[i][0] <= j:
            dp2[i][j] = max(dp2[i+1][j],dp2[i+1][j-data[i][0]]+data[i][1])
        else:
            dp2[i][j] = dp2[i+1][j]

m = 0

for j in range(T):
    for i in range(N):
        if i == 0:
            m = max(m,dp2[i+1][T-1-j] + data[i][1])
        elif i == N-1:
            m = max(m,dp1[i-1][j] + data[i][1])
        else:
            m = max(m,dp1[i-1][j] + dp2[i+1][T-1-j] + data[i][1])

print(m)

Fixed submission:
N,T = map(int,input().split())
data = [0] * N

M = 0
for i in range(N):
    data[i] = list(map(int,input().split()))
    M = max(M,data[i][0])

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

for j in range(T):
    if j < data[0][0]:
        dp1[0][j] = 0
    else:
        dp1[0][j] = data[0][1]

for j in range(T):
    for i in range(1,N):
        if data[i][0] <= j:
            dp1[i][j] = max(dp1[i-1][j],dp1[i-1][j-data[i][0]]+data[i][1])
        else:
            dp1[i][j] = dp1[i-1][j]

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

for j in range(T):
    if j < data[N-1][0]:
        dp2[N-i][j] = 0
    else:
        dp2[N-1][j] = data[N-1][1]

for j in range(T):
    for i in range(N-2,-1,-1):
        if data[i][0] <= j:
            dp2[i][j] = max(dp2[i+1][j],dp2[i+1][j-data[i][0]]+data[i][1])
        else:
            dp2[i][j] = dp2[i+1][j]

m = 0

for j in range(T):
    for i in range(N):
        if i == 0:
            m = max(m,dp2[i+1][T-1-j] + data[i][1])
        elif i == N-1:
            m = max(m,dp1[i-1][j] + data[i][1])
        else:
            m = max(m,dp1[i-1][j] + dp2[i+1][T-1-j] + data[i][1])

print(m)