#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g, dp[5001][5001], i, p[5001], w[5001], cap;
int main()
{
    fin>>n>>g;
    for(i=1; i<=n; i++)
    {
        fin>>w[i]>>p[i];
    }
    cap=g;
    dp[0][cap]=0;
    for(i=1; i<=n; i++)
    {
        for(cap=1; cap<=g; cap++)
        {
          if(w[i]>cap)
            dp[i][cap]=dp[i-1][cap];
        else
        {
            if(dp[i-1][cap]>dp[i-1][cap-w[i]]+p[i])
                 dp[i][cap]=dp[i-1][cap];
             else
                dp[i][cap]=dp[i-1][cap-w[i]]+p[i];
        }

        }

    }
    fout<<dp[n][g]<<" ";
    return 0;
}