include”iostream”

include”cmath”

using namespace std;

const int N = 1005;//最大物品数
int v[N];//体积
int w[N];//价值
int dp[N][N];//dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
int main(){
int n, m;
cin>> n >> m;//输入物品数量和背包容积
for(int i = 1; i <= n; i){
cin >> v[i] >> w[i];//输入物品体积与价值
}
// 动态规划填表
for(int i = 1; i <= n; i){//物品i
for(int j = 1; j <= m; j++){//背包大小j
if(j < v[i]){//背包体积小余物品i体积，不放入物品i
dp[i][j] = dp[i - 1][j];
}
else{//背包体积大于或等于物品i体积
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);//分为两种情况，比较物品i放入的价值高还是不放入价值高，dp[i - 1][j - v[i]]表示为容量为j的背包需要留出这个物品i的容量才可以放物品i，+w[i]表示表示背包放入物品i后的总价值
}
}
}
cout << dp[n][m];

}