#include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 int n, m;

 int dp[maxn];

 int W[], D[];

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (cin >> n >> m && n && m)

     {

         memset(dp, , sizeof(dp));

         for (int i = ; i <= n; i++)

             cin >> W[i] >> D[i];

         for (int i = ; i <= n; i++)

         {

             for (int j = m; j >= W[i]; j--)

             {

                 dp[j] = max(dp[j], dp[j - W[i]] + D[i]);

             }

         }

         cout << dp[m] << endl;

     }

     return ;

 }