#include <iostream>
#include <cstdio>

using namespace std;

int a[10001], w[5001], p[5001], maxi, n, g, s;

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d\n", &n, &g);
    for(int i=1;i<=n;i++)
        scanf("%d %d\n", &w[i], &p[i]);
    a[w[1]]=p[1];
    for(int i=2;i<=n;i++)
        for(int j=g;j>=1;j--)
            if(j > w[i] && a[j - w[i]])
                a[j] = max(a[j], a[j - w[i]] + p[i]);
            else if(j == w[i])
                a[j] = max(a[j], p[i]);
            else a[j] = w[i];
    for(int i=1;i<=g;i++)
        maxi = max(maxi, a[i]);
    printf("%d", maxi);
    return 0;
}