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

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
calc_dict = {}
total = 0
for k, v in combi.items():
  if v in calc_dict:
    combi_count[k] = calc_dict[v]
  else:
    combi_count[k] = combinations_count(v, 2)
    calc_dict[v] = combi_count[k]
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)

### FIXED CODE ###

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return n * (n-1) // 2 
    #math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
calc_dict = {}
total = 0
for k, v in combi.items():
  if v in calc_dict:
    combi_count[k] = calc_dict[v]
  else:
    combi_count[k] = combinations_count(v, 2)
    calc_dict[v] = combi_count[k]
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)
### BUGGY CODE ###

import math
from operator import mul
from functools import reduce

'''
def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return (over // under) % (10 ** 9 + 7)

>TLE
> 竸プロの、nCk mod. p 　パターン
>逆元を利用する。
'''


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


x, y = map(int, input().split())

diff = abs(x - y)
large = max(x, y)
small = min(x, y)

if (small * 2 < large):
    print(0)
    exit()


#ans = diff
large -= diff * 2
small -= diff

if (small % 3 != 0):
    print(0)
    exit()

else:
    num = small / 3
    nn = num * 2 + diff
    #rr = num
    ans = comb(int(nn), int(num), 10 ** 9 + 7)

    print(int(ans))


### FIXED CODE ###

p = 10 ** 9 + 7
x, y = map(int, input().split())

diff = abs(x - y)
large = max(x, y)
small = min(x, y)

if (small * 2 < large):
    print(0)
    exit()


# ans = diff
large -= diff * 2
small -= diff

if (small % 3 != 0):
    print(0)
    exit()


num = int(small / 3)
nn = int(num * 2 + diff)
# rr = num

factorial = [0] * (nn + 1)
factorial[0] = 1
for i in range(nn):
    factorial[i + 1] = factorial[i] * (i + 1) % p


def cmb(n, k):
    # if (n == 1 or k == 1):
    if (n == 0 or k == 0):
        return 1
    if (n < 0 or k < 0):
        return 0

    return factorial[n] * pow(factorial[n - k], p - 2, p) * pow(factorial[k], p - 2, p) % p


ans = cmb(int(nn), int(num))
print(int(ans))
### BUGGY CODE ###

A, B, K = list(map(int, input().split()))
X = [x for x in range(A, B+1)]
sorted_ans = list(sorted(set(X[:K] + X[-K:])))
for x in sorted_ans:
    print(x)

### FIXED CODE ###

A, B, K = list(map(int, input().split()))
ans = set()
for i in range(K):
    if A <= A+i <= B:
        ans.add(A+i)
    if A <= B-i <= B:
        ans.add(B-i)
for x in sorted(ans):
    print(x)
### BUGGY CODE ###

class SegmentTree(object):
    def __init__(self, size, op, id):
        s = 1
        while s < size:
            s *= 2
        self.num_leaves = s
        self.nodes = [id]*(2*s-1)
        self.op = op
        self.id = id
    def update(self, i, x):
        i += self.num_leaves - 1
        self.nodes[i] = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.op(self.nodes[2*i+1], self.nodes[2*i+2])
    def query(self, l, r):
        l += self.num_leaves-1
        r += self.num_leaves-1
        res = self.id
        while l < r:
            if l&1==0:
                res = self.op(res, self.nodes[l])
            if r&1==0:
                r -= 1
                res = self.op(res, self.nodes[r])
            l >>= 1
            r >>= 1
        return res
INF = -float("inf")
def gcd(x,y):
    if x == INF:
        return y
    if y == INF:
        return x
    if x<y:
        x,y = y,x
    r = (x%y)
    while r:
        x,y = y, r
        r = (x%y)
    return y
    
N = int(input())
A = list(map(int,input().split()))
seg = SegmentTree(N, gcd, INF)
for i in range(N):
    seg.update(i, A[i])
ans = INF
for i in range(N):
    ans = max(gcd(seg.query(0,i), seg.query(i+1, N)), ans)
print(ans)


### FIXED CODE ###

INF = -float("inf")
def gcd(x,y):
    if x == INF:
        return y
    if y == INF:
        return x
    if x<y:
        x,y = y,x
    r = (x%y)
    while r:
        x,y = y, r
        r = (x%y)
    return y
    
N = int(input())
A = list(map(int,input().split()))
lgcd = [INF]*N
rgcd = [INF]*N
lgcd[0] = A[0]
rgcd[0] = A[-1]
for i in range(1,N):
    lgcd[i] = gcd(lgcd[i-1], A[i])
    rgcd[i] = gcd(rgcd[i-1], A[N-i-1])
lgcd = [INF]+lgcd
rgcd = [INF]+rgcd
ans = INF
for i in range(N):
    ans = max(ans, gcd(lgcd[i],rgcd[N-i-1]))
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
yn = "YES"

while(len(s) > 0):
    if(s.endswith("dream") or s.endswith("erase")):
        s = s[:(len(s)-5)]
    elif(s.endswith("eraser")):
        s = s[:(len(s)-6)]
    elif(s.endswith("dreamer")):
        s = s[:(len(s)-7)]
    else:
        yn = "NO"

print(yn)

### FIXED CODE ###

s = input()
n = len(s)
yn = "YES"

while(len(s) > 0):
    if(s.endswith("dream") or s.endswith("erase")):
        s = s[:(len(s)-5)]
    elif(s.endswith("eraser")):
        s = s[:(len(s)-6)]
    elif(s.endswith("dreamer")):
        s = s[:(len(s)-7)]
    else:
        yn = "NO"
        break

print(yn)
### BUGGY CODE ###

from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))

acc = [0]+list(accumulate(As))
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 計算
ans = 0
now = 0
for d in range(40,-1,-1):
    cnt = 0
    for s in sums:
        # 上から見て、bitが立っている数がk個以上かどうか
        # 最上位がkこ未満だったら、そのbitはもう使わない
        # 1000 -> 1100 -> 1100 -> 1101 みたいな絞り込み
        if s & (now|(1<<d)) == now|(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now |= 1<<d
print(now)

### FIXED CODE ###

n, k = map(int, input().split())
As = list(map(int, input().split()))

from itertools import accumulate
acc = [0]+list(accumulate(As))
dp = [0] * 50
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 最大の桁数
for d in range(50):
    if max(sums) & (1<<d):
        mx = max(mx, d)
        dp[d] += 1
mx = 0
for i in range(50):
    if dp[i] >= k:
        mx = max(mx,i)

# 計算
ans = 0
now = 0
for d in range(50,-1,-1):
    cnt = 0
    for s in sums:
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)
### BUGGY CODE ###

import sys
from random import randint
from time import time
start = time()
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline


def get_sat():
    sat = 0
    when = [-1] * 26
    for i in range(d):
        sat += s[i][t[i]]
        when[t[i]] = i
        for j in range(26):
            sat -= c[j] * (i - when[j])
    return sat


d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
t = [randint(0, 25) for i in range(d)]
ans = get_sat()
told = t[:]
while time() - start < 1.9:
    p, q = randint(0, d - 1), randint(0, 25)
    t[p] = q
    if ans <= get_sat():
        told = t[:]
    else:
        t = told[:]
print(*t)


### FIXED CODE ###

import sys
from random import randint
from time import time
start = time()
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline


def get_sat():
    sat = 0
    when = [-1] * 26
    for i in range(d):
        sat += s[i][t[i]]
        when[t[i]] = i
        for j in range(26):
            sat -= c[j] * (i - when[j])
    return sat


d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
t = [randint(0, 25) for i in range(d)]
ans = get_sat()
told = t[:]
while time() - start < 1.7:
    p, q = randint(0, d - 1), randint(0, 25)
    t[p] = q
    if ans <= get_sat():
        told = t[:]
    else:
        t = told[:]
for i in t:
    print(i+1)
### BUGGY CODE ###

n = int(input())
slist = []
sinputlist = sorted(list(input()))
s = sinputlist[0]
for a in sinputlist[1:]:
    s += a
slist.append(s)
c = 0
for i in range(n-1):
    lastc = c
    sinputlist = sorted(list(input()))
    s = sinputlist[0]
    for a in sinputlist[1:]:
        s += a
    for b in slist:
        if s == b:
            c += 1
    #if c == lastc:
    slist.append(s)
print(c)


### FIXED CODE ###

import math
n = int(input())
l = ["".join(sorted(input())) for i in range(n)]
l.sort()
c = 0
b = l[0]
ans = 0
for s in l[1:]:
    if s == b:
        c += 1
    else:
        ans += c * (c + 1) * 0.5
        c = 0
    b = s
ans += c * (c + 1) * 0.5
print(int(ans))
### BUGGY CODE ###

n = int(input())
a = input().split()
ans = 1
for i in a:
  ans = ans * int(i)
if ans>1000000000000000000:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = input().split()
ans = 1
for i in a:
  if i=='0':
    ans = 0
    break
for i in a:
  ans = ans * int(i)
  if ans>1000000000000000000:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])

def P(m ,n):
    num = 1
    for i in range(n):
        num *= m-i
    return num



total_num = K
judge = [False]*N
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    judge[0] = True
    node = deque([])
    for edge in ki[0]["eda"]:
        node.append(edge[1])
    while len(node) != 0:
        i = node.popleft()
        judge[i] = True
        if len(ki[i]["eda"]) > 1:
            for edge in ki[i]["eda"]:
                if not judge[edge[1]]:
                    node.append(edge[1])
        total_num *= P(K-2, len(ki[i]["eda"])-1)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
N = int(input())
d = [0]*N
route = [[10**9]*N for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    route[u][v] = w
    route[v][u] = w
    d[u] += 1
    d[v] += 1

g = csgraph_from_dense(route, null_value=10**9)

G = dijkstra(g)
d = d.index(max(d))


ans = [0]*N

for i in range(N):
    if i == d:
        continue
    if G[d][i] % 2 != 0:
        ans[i] = 1
for i in range(N):
    print(ans[i])


### FIXED CODE ###

import collections
N = int(input())
d = [0]*N
route = [set() for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    route[u].add((v, w))
    route[v].add((u, w))
    d[u] += 1
    d[v] += 1
d = d.index(max(d))
q = collections.deque()
q.append((d, 0))

G = [0]*N

while(q):
    x, l = q.popleft()
    for v, w in route[x]:
        G[v] = w + l
        q.append((v, w+l))
        route[v].remove((x, w))
ans = [0]*N

for i in range(N):
    if i == d:
        continue
    if G[i] % 2 == 1:
        ans[i] = 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import math
N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
idx = []
for i in range(N):
  B[A[i]-1] += 1
  if B[A[i]-1] >= 2 and not A[i]-1 in idx:
    idx.append(A[i]-1)

from operator import mul
from functools import reduce

def nCr(n,r):
    if n == 1:
        return 0
    r = min(n-r,r)
    if r == 0:
        return 1
    ov = reduce(mul, range(n, n-r, -1))
    un = reduce(mul, range(1, r+1))
    return ov // un

Cs = []
C = []
Ctot = 0
for j in idx:
  if B[j]-1 >= 2:
    Cs.append(nCr(B[j]-1, 2))
  else:
    Cs.append(0)
  tmp = nCr(B[j], 2)
  C.append(tmp)
  Ctot += tmp
for i in range(N):
  current_idx = A[i]-1
  if current_idx in idx:
    count = Ctot + Cs[idx.index(current_idx)]-C[idx.index(current_idx)]
  else:
    count = Ctot
  print(count)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
def nC2(n):
  return n*(n-1)//2
for i in range(N):
  B[A[i]-1] += 1
Ctot = 0
for i in range(N):
  Ctot += nC2(B[i])
for i in range(N):
  current_idx = A[i]-1
  if B[current_idx] == 1:
    count = Ctot
  else:
    count = Ctot + nC2(B[current_idx]-1) - nC2(B[current_idx])
  print(count)
### BUGGY CODE ###

import functools
import operator

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

old_score = 1
new_score = 1

for i in range(n - k + 1): #iはスタート地点
    old_score = new_score
    new_score = 1
    
    list_ = A[i: i + k] #Aのj番目の要素をかける
    new_score = functools.reduce(operator.mul, list_)

    if i != 0 and old_score < new_score:
        print("Yes")
    elif i != 0 and old_score >= new_score:    
        print("No")

### FIXED CODE ###

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

for i in range(n - k): #iはスタート地点
    old = A[i] #Aのj番目の要素をかける
    new = A[i + k]
    
    if old < new:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N,*A = map(int,open(0).read().split())
write = []
for i in A:
    if i not in write:
        write.append(i)
    else:
        write.remove(i)
print(len(write))        

### FIXED CODE ###

from collections import Counter
N,*A = map(int,open(0).read().split())
ca = Counter(A)
copy_ca = ca.copy()
for i in ca.items():
    if i[1] % 2 == 0:
        del copy_ca[i[0]]
print(len(copy_ca))
### BUGGY CODE ###

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans)


### FIXED CODE ###

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans)
### BUGGY CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            if j < n - 1:
                j += 1
                count += n - j 
            else:
                count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = r = mid

ans = 0
if l == r:
    for i in range(n):
        ans += a[i] * count(a, l, n)[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][i] - 1]) * (m - p[0])
    for i in range(n):
        ans += a[i] * count(a, l, n)[1][i] * 2
print(ans)



    


### FIXED CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
bits = [[0 for _ in range(20)] for _ in range(n)]

for i in range(n):
	for j in range(20):
		bits[i][j] = (a[i] >> j) & 1

ans = 0
bits_sum = [0] * 20

r = 0
for l in range(n):
	r = max(r, l)
	while r < n:
		bits_sum = [bits_sum[j] + bits[r][j] for j in range(20)]
		if max(bits_sum) > 1:
			bits_sum = [bits_sum[j] - bits[r][j] for j in range(20)]
			break
		r += 1
	#print(bits_sum, r)
	ans += r-l
	bits_sum = [bits_sum[j] - bits[l][j] for j in range(20)]
	#print(bits_sum, r)

#ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
bits = [[0 for _ in range(20)] for _ in range(n)]

for i in range(n):
	for j in range(20):
		bits[i][j] = (a[i] >> j) & 1

ans = 0
bits_sum = [0] * 20

r = 0
for l in range(n):
	r = max(r, l)
	while r < n:
		bits_sum = [bits_sum[j] + bits[r][j] for j in range(20)]
		if max(bits_sum) > 1:
			bits_sum = [bits_sum[j] - bits[r][j] for j in range(20)]
			break
		r += 1
	#print(bits_sum, r)
	ans += r-l
	bits_sum = [bits_sum[j] - bits[l][j] for j in range(20)]
	#print(bits_sum, r)

#ans += 1
print(ans)
### BUGGY CODE ###

def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [[[0, []] for i in range(t)] for j in range(n + 1)]
    for i in range(n):
        for j in range(t):
            if j - f[i][0] >= 0 and dp[i][j - f[i][0]][0] + f[i][1] > dp[i][j][0]:
                dp[i + 1][j][0] = dp[i][j - f[i][0]][0] + f[i][1]
                dp[i + 1][j][1] = dp[i][j - f[i][0]][1] + [i]
            else:
                dp[i + 1][j] = dp[i][j]
                dp[i + 1][j][1] = dp[i][j][1][:]
    res = dp[n][t - 1][0]
    ff = [f[i][1] for i in range(n) if not i in dp[n][t - 1][1]]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())