//           _____                  _______                  _____                   _____
//          /\    \                /::\    \                /\    \                 /\    \
//         /::\    \              /::::\    \              /::\____\               /::\    \
//        /::::\    \            /::::::\    \            /:::/    /              /::::\    \
//       /::::::\    \          /::::::::\    \          /:::/    /              /::::::\    \
//      /:::/\:::\    \        /:::/~~\:::\    \        /:::/    /              /:::/\:::\    \
//     /:::/__\:::\    \      /:::/    \:::\    \      /:::/    /              /:::/__\:::\    \
//    /::::\   \:::\    \    /:::/    / \:::\    \    /:::/    /              /::::\   \:::\    \
//   /::::::\   \:::\    \  /:::/____/   \:::\____\  /:::/    /      _____   /::::::\   \:::\    \
//  /:::/\:::\   \:::\    \|:::|    |     |:::|    |/:::/____/      /\    \ /:::/\:::\   \:::\    \
// /:::/  \:::\   \:::\____|:::|____|     |:::|____|:::|    /      /::\____/:::/  \:::\   \:::\____\
// \::/    \:::\  /:::/    /\:::\   _\___/:::/    /|:::|____\     /:::/    \::/    \:::\  /:::/    /
//  \/____/ \:::\/:::/    /  \:::\ |::| /:::/    /  \:::\    \   /:::/    / \/____/ \:::\/:::/    /
//           \::::::/    /    \:::\|::|/:::/    /    \:::\    \ /:::/    /           \::::::/    /
//            \::::/    /      \::::::::::/    /      \:::\    /:::/    /             \::::/    /
//            /:::/    /        \::::::::/    /        \:::\__/:::/    /              /:::/    /
//           /:::/    /          \::::::/    /          \::::::::/    /              /:::/    /
//          /:::/    /            \::::/____/            \::::::/    /              /:::/    /
//         /:::/    /              |::|    |              \::::/    /              /:::/    /
//         \::/    /               |::|____|               \::/____/               \::/    /
//          \/____/                 ~~                      ~~                      \/____/
//I am aqua
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define mp make_pair
#define speed  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fo for(int i=0;i<n;i++) cin>>a[i];
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define l first
#define r second
#define input.txt ifstream fin("input.txt"); ofstream fout("output.txt");
using namespace std;
//---------------------------------------------------------------------------------------------------------------------
const int maxn=1e2+10;
const int maxw=1e5;
//---------------------------------------------------------------------------------------------------------------------
ll n , w[maxn] , v[maxn] , dp[maxn][maxw] ;
//---------------------------------------------------------------------------------------------------------------------
int main()
{
    int n,W;
    cin>>n>>W;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=0;i<=W;i++)
    {
        if(i>=w[0])
            dp[0][i]=v[0];
    }
    ll  mx=dp[0][W];
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j>=w[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            else
                dp[i][j]=dp[i-1][j];
        }
        mx=max(mx,dp[i][W]);
    }
    cout<<mx;
}
//I know that ;
//I know where I am
//Do not think I don't


Measured memory_bytes: 80128