#include <iostream> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int INF = 12881; struct node { int w; int d; }data[3402]; int f[12881]; int main() { //freopen("1.txt", "r", stdin); int n, m; while(cin >> n >> m) { int sum = 0; for(int i = 0; i < n; i++) { cin >> data[i].w >> data[i].d; sum += data[i].w; } sum = min(sum, m); memset(f, -1, sizeof(f)); f[0] = 0; int ans = 0;; for(int i = 0; i < n; i++) { for(int j = sum; j >= data[i].w; j--) { if(f[j - data[i].w] != -1) { f[j] = max(f[j], f[j - data[i].w] + data[i].d); if(f[j] > ans) ans = f[j]; } } } cout << ans << endl; } return 0; }
