#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 main()
{
    int n, k, i, j, c[MAX], r[MAX], dp[MAX2];

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

    for(i = 0; i <= k; i++) dp[i] = 0;

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

    if(k >= c[n]) dp[k] = max(dp[k], r[n] + dp[k-c[n]]);

    fout << dp[k];

    return 0;
}