include <bits/stdc++.h>

define ll long long

using namespace std;

ll n, m;
ll a[1000],b[1000];
ll gt, cn;
ll f[1000][1000];

void nhap()
{
cin>>n>>m;
for(int i=0;i<n;i++){ cin>>a[i]>>b[i];
}
}

void solve()
{
for (int i = 1; i <= n; ++i)
{
for (int w = 1; w <= m; ++w)
{
if (w >= a[i - 1]) // neu co the chon
f[i][w] = max(f[i - 1][w], f[i - 1][w - a[i - 1]] + b[i - 1]);
else
f[i][w] = f[i - 1][w];
}
}

cout << f[n][m];

// for(int i=0;i<n;i++){ // cn+=b[i]; // if(cn>m){
// continue;
// }
// else{
// if(cn<=m){
// cout<<cn;
// }
// }
// }
// }
// }
// }
}

int main()
{
nhap();
solve();

}

asdasdasd