#include <bits/stdc++.h>
using namespace std;

int v[5005], gr[10005];
int dp[10005];

int main() 
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
	int n,g; cin >> n >> g;
    for (int i = 1; i <= n; i ++)
        cin >> gr[i] >> v[i];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = g; j >= 1; j --)
        {
            if (j < gr[i])
                dp[j] = dp[j];
            else
                dp[j] = max(dp[j], dp[j - gr[i]] + v[i]);
        }
    }
    cout << dp[g];
}