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

a, b, k = map(int, input().split())

while k > 0:
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
    elif a == 0 and b == 0:
        continue
    k -= 1

print(a, end=" ")
print(b)

### FIXED CODE ###

a, b, k = map(int, input().split())

new_a = a - k if a >= k else 0
new_b = b - (k - a) if a < k else b
if new_b < 0:
    new_b = 0

print(new_a, end=" ")
print(new_b)
### BUGGY CODE ###

N, A = map(int, input().split())
x = list(map(int, input().split()))
sum_x = sum(x)
X = max(x + [A])

dp = [[[0] * (N * X + 1) for _ in range(N + 1)] for _ in range(N + 1)]

answer = 0
for j in range(N + 1):
    for k in range(N + 1):
        for s in range(N * X + 1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
            else:
                dp[j][k][s] = 0
            if j == N and s == k * A and k >= 1:
                answer += dp[j][k][s]

print(answer)


### FIXED CODE ###

from functools import lru_cache

N, A = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(lambda i: i - A, x))
X = max(max(x), A)

@lru_cache(maxsize=None)
def solve(j, t):
    global y
    if j == 0 and t == 0:
        return 1
    elif j >= 1 and (t < y[j - 1] - N * X or t > y[j - 1] + N * X):
        return solve(j - 1, t)
    elif j >= 1 and t >= y[j - 1] - N * X and t <= y[j - 1] + N * X:
        return solve(j - 1, t) + solve(j - 1, t - y[j - 1])
    else:
        return 0

print(solve(N, 0) - 1)
### BUGGY CODE ###

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

for i in range(M):
  B, C = map(int, input().split())
  for _ in range(B):
    A.append(C)

A.sort(reverse = True)
l = A[0:lenA]

print(sum(l))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
lenA = len(A)
minA = min(A)
BC.sort(reverse = True, key = lambda x:x[1])

i = 0
cnt = 0
while cnt < lenA and i < M:
  A.extend([BC[i][1] for _ in range(BC[i][0])])
  cnt += BC[i][0]
  i += 1
A.sort(reverse = True)
l = A[0:lenA]

print(sum(l))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
for i in range(m // n, 0, -1):
    if m % i == 0:
        print(i)
        exit()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


n, m = map(int, readline().split())
if is_prime(m):
    if n == 1:
        print(m)
    else:
        print(1)
    exit()
for i in range(m // n, 0, -1):
    if m % i == 0:
        print(i)
        exit()
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
if N%K==0:
    print("0")
else:
    while abs(N-K) < N:
        N = abs(N-K)
    print(N)

### FIXED CODE ###

N,K = map(int,input().split())
if N>=K:
    N = N%K
    while abs(N-K) < N:
        N = abs(N-K)
    print(N)
else:
    if K >= 2*N:
        print(N)
    else:
        N = K%N
        print(N)
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = map(int, input().split())
ans = "YES"

for ti in t:
    if ti in d:
        d.remove(ti)
    else:
        ans = "NO"
print(ans)


### FIXED CODE ###

from collections import Counter
n = input()
d = Counter(map(int, input().split()))
m = input()
t = Counter(map(int, input().split()))
d.subtract(t)
print("NO" if -d else "YES")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	man = 0
	syu = 0
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
		if i < K:
			man += d
			if t == 1:
				syu += 1
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		tmp = sorted(osushi_list, key = lambda k:k[1], reverse=True)
		for i, val in enumerate(tmp):
			d, t = val
			syu_local += 1
			man += d
			count += 1
			if syu_local == syu_mokuhyou or count >= K:
				break
					
		tmp = sorted(osushi_list, key = lambda k:k[1])
		for i, val in enumerate(tmp):
			if count >= K:
				break
			d, t = val
			man += d
			count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	sushi_mii = []
	sushi_kii = []
	syu = [[] for i in range(N)]
	for i in range(N):
		t,d = inputMap()
		t -= 1
		syu[t].append(d)

	for i in syu:
		if len(i) > 0:
			i.sort()
			i = i[::-1]
			for j,val in enumerate(i):
				if j == 0:
					sushi_mii.append(val)
				else:
					sushi_kii.append(val)

	sushi_mii.sort()
	sushi_mii = sushi_mii[::-1]
	sushi_kii.sort()
	sushi_kii = sushi_kii[::-1]

	sushi_mi = []
	sushi_ki = []
	for i,val in enumerate(sushi_mii):
		if i == 0:
			sushi_mi.append(val)
		else:
			tmp = sushi_mi[i-1]
			sushi_mi.append(tmp + val)

	for i,val in enumerate(sushi_kii):
		if i == 0:
			sushi_ki.append(val)
		else:
			tmp = sushi_ki[i-1]
			sushi_ki.append(tmp + val)

	ans = 0
	for i in range(1, min(len(sushi_mi), K)+1):
		x = 0
		tmp = 0
		if K - i > len(sushi_ki):
			continue

		tmp += sushi_mi[i-1]
		x = i

		if K - i > 0:
			tmp += sushi_ki[K - i-1]

		oishi = tmp + x * x
		if ans < oishi:
			ans = oishi
	print(ans)

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

a,b,x=map(int,input().split())
numbers=[int(c) for c in range(b+1) if c>=a]
count=0
for d in numbers:
    if d%x==0:
        count+=1
    else:
        pass
print(count)

### FIXED CODE ###

a,b,x=map(int,input().split())
c=a-1
max=b//x+1
min=c//x+1
if c==-1:
    min=0
else:
    pass
print(max-min)
### BUGGY CODE ###



n,k = map(int,input().split())
l = list(map(int,input().split()))
position = 1
for i in range(k):
    position = l[position-1]
print(position)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    roop = [1]
    stayed = [0]*n
    for i in range(n):
        next_city = l[roop[-1]-1]
        if stayed[next_city-1]:
            endindex = i
            for j,r in enumerate(roop):
                if r == next_city:
                    startindex = j
            break
        else:
            roop.append(next_city)
            stayed[next_city-1] = 1

    if k < startindex:
        print(roop[k])
    else:
        dis = endindex - startindex + 1
        a = (k - startindex) % dis
        print(roop[a + startindex])
main()
### BUGGY CODE ###

def merge(array):
    mid = len(array)
    if mid > 1:
        mid = mid // 2
        left = merge(array[:mid])
        right = merge(array[mid:])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] == right[0]:
                print("NO")
                exit()
            elif left[0] < right[0]:
                array.append(left.pop(0))
            else:
                array.append(right.pop(0))
        if len(left) != 0:
            array.extend(left)
        elif len(right) != 0:
            array.extend(right)
    return array

n = int(input())
a = list(map(int, input().split()))
a.sort()
merge(a)
print("YES")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = {}
flag = 0

for i in A:
    if (ans.get(i) != None):
        flag = 1
        break
    else:
        ans[i] = 1

if (flag == 0):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


ans = (100 * 100) + 1


def main():
    global ans
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))

    def search(x, y, cnt):
        global ans
        if cnt > ans:
            return

        if grid[y][x] == "#":
            cnt += 1

        if y == h and x == w:
            ans = min(ans, cnt)
            return
        else:
            if y < h:
                search(x, y + 1, cnt)
            if x < w:
                search(x + 1, y, cnt)
    search(1, 1, 0)
    print(ans)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
S = ''.join(read().decode().split())
 
INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]
 
print(min(dp[-1]))
### BUGGY CODE ###

import math
import copy

a = int(input())

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

lis = [0]*(a+1)

for kk in range(a):
    lis[b[kk]] += 1
    
#print(lis)

for ll in range(a):
    count = 0
    new_list = copy.copy(lis)
    new_list[b[ll]] -= 1
    #print(new_list)
    for pp in range(a):
        if new_list[pp] > 0:
            count += (new_list[pp]*(new_list[pp]-1))/2
    print(int(count))

### FIXED CODE ###

import collections

n = int(input())
lis = list(map(int,input().split()))
 
clis = collections.Counter(lis)

count = 0
for kk in clis.values():
	count += (kk * (kk - 1)) // 2
    
for ll in lis:
	print(count - clis[ll] + 1)
### BUGGY CODE ###

X = input()

for j in range(len(X)):
    X = X.replace('ST', '')
    if 'ST' not in X:
        break

print(len(X))

### FIXED CODE ###

X = input()
s = cnt = 0

for i in range(len(X)):
    if X[i] == 'S':
        s += 1
    elif s != 0:
        cnt += 2
        s -= 1

ans = len(X) - cnt
print(ans)
### BUGGY CODE ###

import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())

dp = np.array([[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)])
dp[:, :, 1] = 0
dp[0:a, :, :] = 0
dp[:, 0:b, :] = 0
dp = list(dp)

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = (i * dp[i][j - 1][0] + dp[i][j - 1][1]) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1])) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)


### FIXED CODE ###

#import numpy as np
import math
import collections
import bisect


def main():
    a, b, c, d = map(int, input().split())

    dp0 = [[1 for i in range(d + 1)] for j in range(c + 1)]
    dp1 = [[0 for i in range(d + 1)] for j in range(c + 1)]
    for i in range(c + 1):
        for j in range(d + 1):
            if j < b or i < a:
                dp0[i][j] = 0
                dp1[i][j] = 0
    for i in range(a, c + 1):
        for j in range(b, d + 1):
            # print(i, j, dp[i][j])
            if a == i and b == j:
                continue
            dp0[i][j] = ((i * dp0[i][j - 1]) % 998244353 + dp1[i][j - 1]) % 998244353
            dp1[i][j] = (j * (dp0[i - 1][j] + dp1[i - 1][j]) % 998244353) % 998244353

    print((dp0[c][d] + dp1[c][d]) % 998244353)


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

# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
s = input()
n = len(s)
dp = [0] * n
mod = 2019
for i in range(n):
    m = int(s[i]) * pow(10, n - i - 1, mod) % mod
    dp[i] = m

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        total = sum(dp[i:j + 1])
        if total % mod == 0:
            ans += 1
print(ans)

### FIXED CODE ###

# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

def nC2(n):
    return n * (n - 1) // 2
s = input()
n = len(s)
dp = [0] * 2020
mod = 2019
temp = 0
dp[0] = 1
for i in range(n):
    m = (int(s[i]) * pow(10, n - i - 1, mod) + temp)% mod
    dp[m] += 1
    temp = m
ans = 0
for i in range(2020):
    if dp[i]:
        ans += nC2(dp[i])
print(ans)
### BUGGY CODE ###

s = input()
t = input()
ls, lt = len(s), len(t)

dp_list = [ [ "" for i in range(ls+1) ] for j in range(lt+1) ]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = "".join([dp_list[i][j], t[i]])
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]
        else:
            a = dp_list[i][j]
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]

print(dp_list[-1][-1])

### FIXED CODE ###

s = input()
t = input()
ls, lt = len(s), len(t)

dp_list = [ [ 0 for i in range(ls+1) ] for j in range(lt+1) ]
index_list = [ [ None for i in range(ls) ] for j in range(lt) ]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = dp_list[i+1][j]
            b = dp_list[i][j+1]
            c = dp_list[i][j] + 1 
            p = [a,b,c].index(max(a,b,c))
            dp_list[i+1][j+1] = [a,b,c][p]
            index_list[i][j] = (1,p)

        else:
            a = dp_list[i+1][j]
            b = dp_list[i][j+1]
            p = [a,b].index(max(a,b))
            dp_list[i+1][j+1] = [a,b][p]
            index_list[i][j] = (0,p)

q = dp_list[-1][-1]
r = t   

a = 10**5

ans = ""
y, x = lt-1, ls-1
while y != -1 and x != -1:
    if index_list[y][x][1] == 2:
        x -= 1
        y -= 1
        ans += s[x+1]
    elif index_list[y][x][1] == 1:
        y -= 1
    elif index_list[y][x][1] == 0:
        x -= 1

print(ans[::-1])
### BUGGY CODE ###

import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                secondary[j] = max(primary[j], match)
            else:
                secondary[j] = max(secondary[j-1], primary[j],
                                   primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    i = 2 * int(input())
    s = ['', '']
    for line in sys.stdin:
        s[i % 2] = line.strip()
        if i % 2 == 1:
            print(len_lcs(*s))
        i -= 1


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()
### BUGGY CODE ###

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

x = 1
for i in range(0,n):
    x *= a[i]

if x > 10**18:
    print(-1)
    exit()
print(x)


### FIXED CODE ###

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

x = 1
a.sort()
for i in range(0,n):
    x *= a[i]
    if x > 10**18:
        print(-1)
        exit()

print(x)
### BUGGY CODE ###

n=int(input())
x=0
for a in range(1,n):
  for b in range(1,n):
    if a*b<n:
      x+=1
    elif a*b>=n:
      break
print(x)

 

### FIXED CODE ###

n=int(input())
x=0
for a in range(1,n):
  for b in range(1,n):
    if a*b<n:
      x+=1
    elif a*b>=n:
      break
print(x)
### BUGGY CODE ###

import bisect

def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    ans_list = [[0 for i in range(width)] for j in range(high)]

    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                ans_list[i][j] = ans_list[i][j - 1] + 1
        for j in range(width - 1)[::-1]:
            if data[i][j] == '.':
                ans_list[i][j] = max(ans_list[i][j], ans_list[i][j + 1])

    # for i in range(high):
    #     print(ans_list[i])
    # print('---')

    ans_list2 = [[0 for i in range(width)] for j in range(high)]

    for j in range(width):
        for i in range(high):
            if data[i][j] == '.':
                ans_list2[i][j] = ans_list2[i - 1][j] + 1
        for i in range(high - 1)[::-1]:
            if data[i][j] == '.':
                ans_list2[i][j] = max(ans_list2[i][j], ans_list2[i + 1][j])

    ans = 0

    for i in range(high):
        for j in range(width):
            kari = ans_list[i][j] + ans_list2[i][j] - 1
            ans = max(ans, kari)

    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect

def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    ans_list = [[0 for i in range(width)] for j in range(high)]

    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                ans_list[i][j] = ans_list[i][j - 1] + 1
        for j in range(width - 1)[::-1]:
            if data[i][j] == '.':
                ans_list[i][j] = max(ans_list[i][j], ans_list[i][j + 1])

    # for i in range(high):
    #     print(ans_list[i])
    # print('---')

    ans_list2 = [[0 for i in range(width)] for j in range(high)]

    for j in range(width):
        for i in range(high):
            if data[i][j] == '.':
                ans_list2[i][j] = ans_list2[i - 1][j] + 1
        for i in range(high - 1)[::-1]:
            if data[i][j] == '.':
                ans_list2[i][j] = max(ans_list2[i][j], ans_list2[i + 1][j])

    ans = 0

    for i in range(high):
        for j in range(width):
            kari = ans_list[i][j] + ans_list2[i][j] - 1
            ans = max(ans, kari)

    print(ans)



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


from collections import defaultdict

S = input()
n = len(S)

mod = 2019
d = defaultdict(int)
d[0] = 1
num = 0
for i in reversed(range(n)):
    num += int(S[i]) * 10 ** (n - i - 1)
    num %= mod
    d[num] += 1

ans = 0
for v in d.values():
    ans += v * (v - 1) // 2
print(ans)


### FIXED CODE ###


S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

from operator import itemgetter

N, T = [int(i) for i in input().split()]

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

data.sort(key=itemgetter(0))

dp = [dict() for _ in range(N)]
for i in range(T):
    dp[0][i] = 0

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = max(dp[i][T-1] + add_value, dp[i-1][T])
print(dp[-1][T])


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

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

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)