#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 5005
#define MAX2 10005

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[MAX][MAX2];

int main()
{
    int n, k, i, j, c[MAX], r[MAX];

    fin >> n >> k;
    for(i = 1; i <= n; i++) fin >> c[i] >> r[i];

    for(i = 1; i <= n; i++)
        for(j = 1; j <= k; j++)
        {
            if(j >= c[i]) dp[i][j] = max(dp[i-1][j], r[i] + dp[i-1][j-c[i]]);
            else dp[i][j] = dp[i-1][j];
        }

    fout << dp[n][k];

    return 0;
}