#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <locale>
#include <vector>
#include <string>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long ll;

ll w[105];
ll v[105];
ll dp[10000005];
int n;
ll W;

void bag()
{
    for(int i=1; i<=n; i++)
        for(ll j=W; j>=w[i]; j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}

int main()
{

    while(~scanf("%d%lld",&n,&W))
    {
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&w[i],&v[i]);
        memset(dp,0,sizeof dp);
        bag();
        printf("%lld\n",dp[W]);
    }
    return 0;
}
