/*
Name:22-knapsackProblem.cpp
Description:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式:
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式:
输出一个整数，表示最大价值。

数据范围
    0<N,V≤1000
    0<vi,wi≤1000
输入样例
    4 5
    1 2
    2 4
    3 4
    4 5

*/

include [HTML_REMOVED]

define N 1010

using namespace std;

struct Object{
int w;//weight
int v;//value
}obj[N];

struct Knapsack{
int tv;//total value
int o[N];
}kps[N];

int n,w;

int load(){
for(int i = 1; i<=w; i){
kps[i] = kps[i - 1];//把承重为i-1的背包中的最大价值和已经装那些物品，给i这个背包，做为初值
for(int j = 1; j<=n; j){
if(obj[j].w <= i){//逐个试物品看能不能装进去，只要物品的重小于或等背包的最大负载就可以装。
if(kps[i - obj[j].w].o[j] == 0) {//说明在kps[i - obj.w]中还没有装是j这个物品
if(kps[i - obj[j].w].tv + obj[j].v >kps[i].tv ){//在 kps[i - obj.w]如果装第j个物品的总价值大于原来的，那么就装
kps[i] = kps[i - obj[j].w];
kps[i].tv += obj[j].v;
kps[i].o[j] = 1;
}
}
}
}
}
return kps[w].tv;

}

int main(){
scanf(“%d%d”,&n,&w);

for(int i = 1; i <= n; i++){
    scanf("%d%d",&obj[i].w,&obj[i].v);
}   
int res = load();//result
printf("%d",res);
return 0;

}