#include <bits/stdc++.h> using namespace std; const int N=1000+10; int w[N],v[N]; long long f[2][100010]; int main(){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++){ cin >> w[i] >> v[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j>=w[i]){ f[i%2][j]=max(f[(i-1)%2][j],v[i]+f[(i-1)%2][j-w[i]]); }else{ f[i%2][j]=f[(i-1)%2][j]; } } } cout << f[n%2][m]<<endl; return 0; }
