#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NMax 10005
using namespace std;
int n,G;
int w[NMax / 2],v[NMax],p[NMax / 2];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&G);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d",&w[i],&p[i]);
    }
    int f = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = G; j >= w[i]; --j){
            v[j] = max(v[j],v[j-w[i]] + p[i]);
        }
    }
    printf("%d",v[G]);
    return 0;
}