950 B | 950 chars
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull>> ullv2;
ll N, maxWeight,ans;
ll D[2][11000];
ll weight[110], cost[110];
ll max(ll a, ll b) {
return a>b?a:b;
}
void input() {
cin >> N >> maxWeight;
for(int x=1; x<=N; x++) {
cin >> weight[x] >> cost[x];
}
}
void knapsack() {
for(int x=1; x<=N; x++) {
for(int y=0; y<=maxWeight; y++) {
if(y>=weight[x]) {
D[x%2][y] = max(D[(x+1)%2][y],D[(x+1)%2][y-weight[x]]+cost[x]);
}
else {
D[x%2][y] = D[(x+1)%2][y];
}
ans = max(ans, D[x%2][y]);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
knapsack();
cout << ans;
}