/*
背包问题: 有限容积
分析
状态集合
f[i][j] 在最大容积为j的情况下,从前i件物品中选择得到的最大价值
状态划分
不选择当前物品
选择当前物品
选择k件
优化 一层遍历
f[i][j] = max (f[i][j], f[j - v[i] * 1] , f[j - v[i] * 2], f[j - v[i] * 3)
f[i][j - v[i]]= max ( f[i][j - v[i]], f[j - v[i] * 2] , f[j - v[i] * 3)+w[i]*/
include[HTML_REMOVED]
using namespace std;
const int N = 1010;
int w[N], v[N];
int f[N];
int main(){
int n, max_v;
cin>>n>>max_v;
for(int i = 1 ; i <=n ;i)
cin>>v[i]>>w[i];
for(int i = 1; i<= n; i)
for(int j = v[i] ; j <= max_v;j++){
f[j] = max(f[j], f[j-v[i]]+w[i]);
}
cout<<f[max_v];
}