knapsack-dynamic2.cpp

#include<iostream>

int main() {
	int data[100][2];
	int p[100];

	int howmany, mass;
	std::cin >> howmany >> mass;
	for(int i=0; i<=mass; i++) p[i] = 0;
	
	for(int i=1; i<=howmany; i++) {
		std::cin >> data[i][0] >> data[i][1];
	}
	
	for(int i=1; i<=mass; i++) {
		for(int l=1; l<=howmany; l++) {
			if(i >= data[l][1]) p[i] = std::max(p[i], p[i-data[l][1]]+data[l][0]);
		}
		//std::cout << "\n";
	}
	//for(int i=0; i<=mass; i++)	std::cout << p[i] << "\n";
	std::cout << p[mass] << "\n";
}