#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define cin fin
#define cout fout

#define N 5005
int n, gmax, i, j, a[N][N*2], v[N], g[N];

int main()
{
    cin >> n >> gmax ;
    for(i = 1 ; i <= n ; i++)
    {
        cin >> g[i] >> v[i];
    }
    for(i = 1 ; i <= n ; i++)
    {
        for(j = 1 ; j <= gmax ; j++)
        {
            if(j >= g[i])a[i][j] = max(a[i-1][j],a[i-1][j-g[i]]+v[i]);
            else a[i][j] = a[i-1][j];
        }
    }
    cout << a[n][gmax] ;
    return 0;
}