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

n = int(input())
a = int(n**0.5+1)
for i in range(1, n+1):
    ans = 0
    for x in range(1, a):
        for y in range(x, a):
            for z in range(y, a):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i and x == y == z:
                    ans += 1
                elif x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    ans += 3
    print(ans)

### FIXED CODE ###

n = int(input())
a = int(n**0.5+1)
ans = [0]*n
for x in range(1, a):
    for y in range(1, a):
        for z in range(1, a):
            if x**2 + y**2 + z**2 + x*y + y*z + z*x <= n:
                ans[x**2 + y**2 + z**2 + x*y + y*z + z*x -1] += 1
[print(i) for i in ans]
### BUGGY CODE ###

N,K=map(int,input().split())
MOD=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().split())
    S.append((L,R))
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if L>=i:
            continue
        l=max(0,i-R)
        r=min(i-1,i-L)
        dp[i]+=sum(dp[l:r+1])
        dp[i]%=MOD
print(dp[N]%MOD)

### FIXED CODE ###

N,K=map(int,input().split())
MOD=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().split())
    S.append((L,R))
S.sort()
dp=[0]*(N+1)
dp[1]=1
ans=[0]*(K+1)
for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if L>=i:
            break
        l=max(0,i-R)
        r=min(i-1,i-L)
        ans[j]+=dp[r]-dp[l-1]
    dp[i]+=sum(ans)
    dp[i]%=MOD
print(dp[N]%MOD)
### BUGGY CODE ###

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

  m = 10 ** 18
  ans = A[0]

  for i in range(1, N):
    ans *= A[i]

  if(ans > m):
    ans = -1

  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

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

  A.sort()

  m = 10 ** 18
  ans = A[0];

  if(A[0] == 0):
    ans = 0;
  else:
    for i in range(1, N):
      ans *= A[i]

      if(ans > m):
        ans = -1
        break

  print(ans)

if __name__ == "__main__":
  main()
### BUGGY CODE ###

#import numpy as np
import math
n = int(input())
a= list(map(int,input().split()))

ans = a[0]

for i in range(1,n):
    if a[i] == 0:
        print("0")
        exit()
    elif a[i] > 10**18:
        print("-1")
        exit()
    else:
        ans *= a[i]

if ans > 10**18:
    ans = -1
print(ans)
    
    

### FIXED CODE ###

#import numpy as np
import math
n = int(input())
a= list(map(int,input().split()))
a.sort(reverse=1)

ans = a[0]

for i in range(1,n):
    if a[-1] == 0:
        print("0")
        exit()
    elif a[i] > 10**18:
        print("-1")
        exit()
    elif ans > 10**18:
        print("-1")
        exit()
    else:
        ans *= a[i]

if ans > 10**18:
    ans = -1
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 1
if N == 1:
    if A[0] == 0:
        ans = 1
    else:
        print(0)

if N % 2 == 0:
    for i in range(1, int(N/2)+1):
        if A.count(i*2-1) == 2:
            ans *= 2
            ans %= 1000000007
        else:
            ans *= 0
else:
    if A.count(0) == 1:
        for i in range(1, int(N/2)+1):
            if A.count(i*2) == 2:
                ans *= 2
                ans %= 1000000007
            else:
                ans *=0
    else:
        ans *= 0
print(ans)


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
A.sort()
A = collections.Counter(A)

ans = 1
count = 0
if N == 1:
    if A[0] == 1:
        ans = 1
    else:
        ans = 0

elif N % 2 == 0:
    for i in range(1, int(N/2)+1):
        if A[i*2-1] == 2:
            count += 1
        else:
            ans = 0
else:
    if A[0] == 1:
        for i in range(1, int(N/2)+1):
            if A[i*2] == 2:
                count += 1

            else:
                ans = 0
    else:
        ans = 0
for i in range(count):
    ans *= 2
    ans %= 1000000007
print(ans)
### BUGGY CODE ###

#ABC 122 C - GeT AC 18:47

n, q = map(int, input().split())
s = input()
memo = [0]*(n) #与えられた文字列の何文字目にACが現れるかメモ
for i in range(n-1):
    if s[i:i+2] == 'AC':
        memo[i] = 1

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    temp = memo[l:r+1]
    res = sum(temp)
    if temp[-1] == 1:
        res -= 1
    print(res)

### FIXED CODE ###

#ABC 122 C - GeT AC 18:47
n, q = map(int, input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)
for i in range(q):
    l,r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

x, y, z, K = map(int, input().split())
K = min(x * y * z, K)
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)


def check(p):
    cnt = 0
    for i in a:
        for j in b:
            for k in c:
                if i + j + k < p:
                    break
                cnt += 1
                if cnt >= K:
                    return True
    return False


left = 10**10 * 3
right = 0

while left - right > 1:
    center = (left + right) // 2
    if check(center):
        tmp = center
        right = center
    else:
        left = center

cnt = 0
results = []
for i in a:
    for j in b:
        for k in c:
            ijk = i + j + k
            if ijk < tmp:
                break
            results.append(ijk)
            cnt += 1
            if cnt >= K:
                print("\n".join(map(str, sorted(results, reverse=True))))
                exit()


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###


import numpy as np
from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix
N, M = map(int,input().split())
l = [[0]*(N) for _ in range(N)]
for i in range(M):
    A, B = map(int,input().split())
    l[A-1][B-1] = 1
    l[B-1][A-1] = 1

csr = csr_matrix(l)
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)

### FIXED CODE ###

from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix, coo_matrix
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
D = [1] * M
csr = coo_matrix((D, (A, B)), (N, N)).tocsr()
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)
### BUGGY CODE ###

import itertools

def mod(x):
  return x%((10**9)+7)
n=int(input())
a_list=list(map(int,input().split()))
sum_list=[]
for i in itertools.combinations(a_list,2):
  sum_list.append((i[0]*i[1]))

s=sum(sum_list)
s=mod(s)
print(s)

### FIXED CODE ###

import itertools

n=int(input())
a_list=list(map(int,input().split()))
sum=0
ps = list(itertools.accumulate(a_list))
for i in range(n-1):
  sum+=a_list[i]*(ps[n-1]-ps[i])

s=sum%(10**9+7)
print(s)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if not i:
        k += 1
        continue
    if i == n:
        klst.append(k)
        k += 1
    else:
        k += i

for i in klst:
    print(i, al[i] ^ bl[0])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

a=int(input())
l=[int(i) for i in input().split()]
mul=1
for i in l:
    mul*=i
if mul>10**18:
    print(-1)
else:
    print(mul)
    

### FIXED CODE ###

a=int(input())
l=[int(i) for i in input().split()]
mul=1
f=0
if 0 in l:
    print(0)
else:
    for i in l:
        mul*=i
        if mul>10**18:
            f=1
            print(-1)
            break
    if f==0:
        print(mul)
### BUGGY CODE ###

import sys
#n = int(input())
n = int(sys.stdin.readline())
#A = list(map(int,input().split()))
A = list(map(int,sys.stdin.readline().split()))
for i in range(n):
  print(A.index(i+1) + 1,end=" ")

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
line = np.ndarray((n,2),np.int64)
for i in range(n):
  line[i][0] = i + 1
  line[i][1] = a[i]

s = sorted(line,key=lambda x:x[1])
for i in range(n):
  print(s[i][0])
### BUGGY CODE ###

s = list(input())
q = int(input())

qq = [list(input().split()) for i in range(q)]
qq.append([0, 0, 0])

order = 0
cnt = 0
f = []

for i in qq:
  if i[0] != order:
    if order == 1:
      if cnt%2 == 1:
        s.reverse()
        cnt = 0
    elif order == 21:
      s = f + s
      f = []
    else:
      s = s + f
      f = []


  if i[0] == '1':
    order = 1
    cnt += 1
  else:
    if i[1] == '1':
      order = 21
      f.insert(0, i[2])
    else:
      order = 22
      f.append(i[2])

print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

qq = [list(input().split()) for i in range(q)]


rl = 1
rlrl = 1
fleft = deque()
fright = deque()

for i in qq:
  if i[0] == '1':
    rl *= -1
  else:
    if i[1] == '1':
      if rl == 1:
        fleft.appendleft(i[2])
      else:
        fright.append(i[2])
    else:
      if rl == 1:
        fright.append(i[2])
      else:
        fleft.appendleft(i[2])

fleft.reverse()        
        
s.extendleft(fleft)
s.extend(fright)        

if rl == -1:
  s.reverse()

print(''.join(s))
### BUGGY CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    dp = [[min(i, N-1-i)] * N for i in range(N)]
    people = [[True] * N for i in range(N)]
    for j in range(N):
        x = min(j, N-1-j)
        for i in range(N):
            dp[i][j] = min(dp[i][j], x)

    def bfs(sy, sx):
        que = deque([(sy, sx, dp[sy][sx])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):
                ny = y + dy
                nx = x + dx
                if 0 <= ny < N and 0 <= nx < N:
                    if dp[ny][nx] > cur:
                        dp[ny][nx] = cur
                        append((ny, nx, cur))

    answer = 0
    for p in P:
        p -= 1
        i = p // N
        j = p % N
        answer += dp[i][j]
        people[i][j] = False
        bfs(i, j)

    print(answer)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

    print(answer)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def solve(n):
    res = set()
    for i in range(2, n):
        while n % i == 0:
            res.add(i)
            n /= i
    res.add(1)
    return res


A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))

### FIXED CODE ###

from math import sqrt


def solve(n):
    res = set()
    for i in range(2, int(sqrt(n))+1):
        while n % i == 0:
            res.add(i)
            n /= i
        if(n<=1): break
    if n>1:
        res.add(n)
    res.add(1)
    return res


A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))
### BUGGY CODE ###

n, x = map(int, input().split())
while 1:
    if n == 0 and x == 0:
        break
    s = []
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if i + j + k == x\
                and i != j != k\
                and i != j and i != k and j != k:
                    sort = sorted([i, j, k])
                    if sort not in s:
                        s.append(sort)
    print(len(s))
    n, x = map(int, input().split())

### FIXED CODE ###

import itertools
while True:
    n, x = map(int, input().split())
    if n == 0\
    and x == 0:
        break

    a = [i for i in range(1, n+1)]
    b = [i for i in itertools.combinations(a, 3)]
    c = 0
    cnt = 0
    for i in range(len(b)):
        for j in range(3):
            c += b[i][j]
        if c == x:
            cnt += 1
        c = 0
    print(cnt)
### BUGGY CODE ###

import sys

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

ans = 1
for num in A:
    ans *= num

if ans > 10 ** 18:
        print(-1)
        sys.exit()
print(ans)

### FIXED CODE ###

import sys

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

ans = 1
if 0 in A:
    print(0)
    sys.exit()
    
for num in A:
    ans *= num
    if ans > 10 ** 18:
        print(-1)
        sys.exit()
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k = I()
    r = 0
    for a,b,c in itertools.combinations_with_replacement(range(1,k+1), 3):
        g = fractions.gcd(fractions.gcd(a,b), c)
        if a == b:
            if b == c:
                r += g
            else:
                r += g * 3
        elif b == c:
            r += g * 3
        else:
            r += g * 6

    return r


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k = I()
    r = 0
    for a,b,c in itertools.product(range(1,k+1), repeat=3):
        r += math.gcd(math.gcd(a,b), c)

    return r


print(main())
### BUGGY CODE ###

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

for i in range(N):
        tmp = A[i]
        flag = 1 
        for j in range(N):
                if i == j:
                        continue
                if tmp % A[j] == 0:
                        flag = -1
                        break
                if tmp < A[j]:
                        break
        if flag == 1:
                cnt += 1

print(cnt)   

### FIXED CODE ###

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

A.sort()

l = [0] * (A[N - 1] + 1)

for i in A:
        j = i 
        while j <= A[N - 1]: 
                l[j] += 1
                j += i 

cnt = 0 
for k in A:
        if l[k] == 1:
                cnt += 1

print(cnt)
### BUGGY CODE ###

import math
import sys
import collections
def main():
    N=int(input())
    Tr=tuple(input())
    R=[]
    G=[]
    B=[]
    for i in range(N):
       if Tr[i]=="R":
           R.append(i)
       if Tr[i]=="G":
           G.append(i)
       if Tr[i]=="B":
           B.append(i)
    cnt=0
    for i in R:
        for j in G:
            
            for k in B:
                if max(i,j,k)-(i+j+k-max(i,j,k)-min(i,j,k))!=(i+j+k-max(i,j,k)-min(i,j,k))-min(i,j,k):
                    cnt+=1

    print(cnt)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import sys
import collections

def main():
    N=int(input())
    Tr=list(input())
    R=[]
    G=[]
    B=[]
    for i in range(N):
       if Tr[i]=="R":
           R.append(i)
           continue
       if Tr[i]=="G":
           G.append(i)
           continue
       if Tr[i]=="B":
           B.append(i)
           continue
    cnt=len(R)*len(G)*len(B)
    for j in range(N):
        for i in range(j):
            if 2*j-i<=N-1:
                if Tr[2*j-i]!=Tr[i] and Tr[2*j-i]!=Tr[j] and Tr[j]!=Tr[i]:
                    cnt-=1
    print(cnt)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))

def lcm(n, m):
    return n // fractions.gcd(n, m) * m

LCM = a[0]
for i in range(1, n):
    LCM = lcm(a[i], LCM)

res = 0
MOD = 1000000007
for i in range(n):
    res = (res + LCM//a[i]) % MOD
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
def gcd(n, m):
    if(m): return gcd(m, n%m)
    else: return n
 
def lcm(n, m):
    return n // gcd(n, m) * m
 
LCM = a[0]
for i in range(1, n):
    LCM = lcm(a[i], LCM)
 
res = 0
MOD = 1000000007
for i in range(n):
    res += LCM//a[i]
    
print(res % MOD)
### BUGGY CODE ###


def main():
    
    
    in1 = [int(e) for e in input().split()]
    n = in1[0]
    q = in1[1]

    a = []
    b = []
    for i in range(n-1):
        in1 = [int(e) for e in input().split()]
        a.append(in1[0])
        b.append(in1[1])

    p = []
    x = []
    for i in range(q):
        in1 = [int(e) for e in input().split()]
        p.append(in1[0])
        x.append(in1[1])

    l = []
    for i in range(n):
        l.append(0)

    def addval(p,x):
        l[p-1] += x

        for j in range(n-1):
            #print('j',j)
            if(a[j] == p):
                addval(b[j],x)

    for i in range(q):
        addval(p[i],x[i])

    
    for i in range(n):
        print(l[i], end="")
        print(" ", end="")
        




if __name__ == "__main__":
    main()


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

dp1 = [[0] * (T) for _ in range(N + 1)]

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)

### FIXED CODE ###

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

dp1 = [[0] * (T) for _ in range(N + 1)]

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)