1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

import sys

 

n, k = map(int, sys.stdin.readline().rstrip().split())

 

arr = []

dp = [[0] * (k + 1) for _ in range(n)]

for i in range(n):

    w, v = map(int, sys.stdin.readline().rstrip().split())

    arr.append([w, v])

 

for i in range(n):

    for j in range(1, k + 1):

        if i == 0 and j >= arr[i][0]:

            dp[i][j] = arr[i][1]

        elif j < arr[i][0]:

            dp[i][j] = dp[i – 1][j]

        else:

            dp[i][j] = max(arr[i][1] + dp[i – 1][j – arr[i][0]], dp[i – 1][j])

 

print(dp[n – 1][k])