/
多重背包问题：就是枚举出各种状态，实际上就是各种集合，闫老师真心讲的不错，利用max（）函数挑选出最大价值的选取方案，在每一层，分别有不选第i件物品的方案，有选一件的，有选两件的，总之条件限制是总体积不超过m；
公式就是 f[i][j]=max(f[i][j],f[i-1][j-v[i]k]+k*w[i]);

*/

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        for(int k=0;k*v[i]<=j;k++){

            f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);  //不选第I件物品是f[i][j],选第[i]件物品是f[i-1][j-k*v[i]];

        }
    }
}
cout<<f[n][m]<<endl;
return 0;

}