#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[1001][1001], curr_w[1001], p[1001];

int main()
{
    ios_base::sync_with_stdio(false);
    int n, w, i, j, ans;
    fin>>n>>w;
    for (i=1;i<=n;++i)
    {
        fin>>curr_w[i]>>p[i];
        for (j=0;j<=w;++j)///iterez prin greutatile din dp[i-1]
        {
            if (dp[i-1][j]>dp[i][j])
                dp[i][j]=dp[i-1][j];
            if (j+curr_w[i]<=w && dp[i-1][j]+p[i]>dp[i][j+curr_w[i]])
                dp[i][j+curr_w[i]]=dp[i-1][j]+p[i];
        }
    }
    fin.close();
    ans=0;
    for (i=0;i<=w;++i)
        if (dp[n][w]>ans)
            ans=dp[n][w];
    fout<<ans;
    fout.close();

    return 0;
}