#include<cstdio>
#include <cstring>

using namespace std;

int v[10010], v1[10010];
int n, g;

struct obiect
{
    int g, val;
}obj;

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", &obj.g, &obj.val);
        for(int j = 1; j <= g; j ++)
            if(j < obj.g)
                v1[j] = v[j];
            else
                if(v[j] < v[j - obj.g] + obj.val)
                    v1[j] = v[j - obj.g] + obj.val;
                else
                    v1[j] = v[j];
        memcpy(v, v1, sizeof(v1));
    }
    printf("%d\n", v1[g]);
}