#include <fstream>

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int n, g, v[5001], G[10001], dp[100000001], mx, g1;
int main()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        fin >> G[i] >> v[i];
        mx += G[i];
    }
    for (int i = 0; i <= g; i++)
    {
        dp[i] = -1;
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int cg = g - G[i]; cg >= 0; cg--)
        {
            if (dp[cg] != -1)
            {
                dp[cg + G[i]] = max(dp[cg + G[i]], dp[cg] + v[i]);
            }
        }
    }
    int fin = 1e9;
    for (int i = g; i <= g + mx; i++)
    {
        if (dp[i] > 0)
            if (max(dp[i], fin) == fin)
            {
                fin = dp[i];
                g1 = i;
            }
    }
    fout << fin;
    return 0;
}