#include <bits/stdc++.h>
using namespace std;
int n, G, i, j, v[5005], g[5005], dp[10005];
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d %d", &n, &G);
    for(i = 1; i <= n; i ++)
        scanf("%d %d", &g[i], &v[i]);
    for(i = 1; i <= n; i ++)
        for(j = G; j >= g[i]; j --)
            dp[j] = max(dp[j], dp[j - g[i]] + v[i]);
    printf("%d", dp[G]);
    return 0;
}