//二维版本
/*
include[HTML_REMOVED]
using namespace std;
const int N=1010;
int n,m;//表示物品和容量
int v[N],w[N];//体积和价值
int f[N][N];//dp数组,表示前i个物品,体积不超过j的选法的集合
//表示集合的属性为价值的最大值
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=1;j<=m;j++)
{
if(v[i]>j)f[i][j]=f[i-1][j];//当装不下时,只能选择不选
else
{
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
/
//优化后的一维版本
/
include[HTML_REMOVED]
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//以为dp数组
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=m;j>=1;j--)
{
if(v[i]>j)f[j]=f[j];
else
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
}
cout<<f[m]<<endl;
return 0;
}
*/
//输入上的优化,不必再开两个数组
include[HTML_REMOVED]
using namespace std;
const int N=1010;
int n,m;
int v,w;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v>>w;
for(int j=m;j>=v;j--)
{
f[j]=max(f[j],f[j-v]+w);
}
}
cout<<f[m]<<endl;
return 0;
}