// https://w...content-available-to-author-only...j.com/problems/KNAPSACK/
// Top-down, dynamic programming knapsack implementation.
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
using namespace std;
#define INF 1e9
// State of the problem. First: index of current element on items vector. Second: capacity remaining.
typedef pair<int, int> state;
struct Item {
int size;
int value;
};
vector<Item> items;
int N;
map<state, int> memo;
// index: index of the current item being considered in the 'items' vector.
// capacity: capacity remaining in the knapsack.
int knapsack(int index, int capacity) {
if (index == N || capacity == 0) // base cases of recursion.
return 0;
state cs = state(index, capacity); // current state of the problem.
if (memo.count(cs)) // if state already visited, return its value.
return memo[cs];
int newcap = capacity - items[index].size; // new capacity if current item is chosen.
int xa = -INF, xb; // just variables for store the recursive calls result.
xb = knapsack(index + 1, capacity); // if not to chose the current item.
if (newcap >= 0) // if current item fits in the current remaining capacity:
xa = knapsack(index + 1, newcap) + items[index].value; // value if chose the current item.
int res = max(xa, xb); // memoize and return the maximum of both possible choices.
memo[cs] = res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S;
cin >> S >> N;
items = vector<Item>(N);
for (int i = 0; i < N; i++) {
cin >> items[i].size >> items[i].value;
}
cout << knapsack(0, S) << "\n";
return 0;
}
Ly8gaHR0cHM6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5qLmNvbS9wcm9ibGVtcy9LTkFQU0FDSy8KLy8gVG9wLWRvd24sIGR5bmFtaWMgcHJvZ3JhbW1pbmcga25hcHNhY2sgaW1wbGVtZW50YXRpb24uCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxtYXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIElORiAxZTkKCi8vIFN0YXRlIG9mIHRoZSBwcm9ibGVtLiBGaXJzdDogaW5kZXggb2YgY3VycmVudCBlbGVtZW50IG9uIGl0ZW1zIHZlY3Rvci4gU2Vjb25kOiBjYXBhY2l0eSByZW1haW5pbmcuCnR5cGVkZWYgcGFpcjxpbnQsIGludD4gc3RhdGU7ICAKCnN0cnVjdCBJdGVtIHsKCWludCBzaXplOwoJaW50IHZhbHVlOwp9OwoKdmVjdG9yPEl0ZW0+IGl0ZW1zOwoKaW50IE47CgptYXA8c3RhdGUsIGludD4gbWVtbzsKCi8vIGluZGV4OiBpbmRleCBvZiB0aGUgY3VycmVudCBpdGVtIGJlaW5nIGNvbnNpZGVyZWQgaW4gdGhlICdpdGVtcycgdmVjdG9yLgovLyBjYXBhY2l0eTogY2FwYWNpdHkgcmVtYWluaW5nIGluIHRoZSBrbmFwc2Fjay4KaW50IGtuYXBzYWNrKGludCBpbmRleCwgaW50IGNhcGFjaXR5KSB7CglpZiAoaW5kZXggPT0gTiB8fCBjYXBhY2l0eSA9PSAwKSAgLy8gYmFzZSBjYXNlcyBvZiByZWN1cnNpb24uCgkJcmV0dXJuIDA7CglzdGF0ZSBjcyA9IHN0YXRlKGluZGV4LCBjYXBhY2l0eSk7ICAvLyBjdXJyZW50IHN0YXRlIG9mIHRoZSBwcm9ibGVtLgoJaWYgKG1lbW8uY291bnQoY3MpKSAgLy8gaWYgc3RhdGUgYWxyZWFkeSB2aXNpdGVkLCByZXR1cm4gaXRzIHZhbHVlLgoJCXJldHVybiBtZW1vW2NzXTsKCWludCBuZXdjYXAgPSBjYXBhY2l0eSAtIGl0ZW1zW2luZGV4XS5zaXplOyAgIC8vIG5ldyBjYXBhY2l0eSBpZiBjdXJyZW50IGl0ZW0gaXMgY2hvc2VuLgoJaW50IHhhID0gLUlORiwgeGI7ICAvLyBqdXN0IHZhcmlhYmxlcyBmb3Igc3RvcmUgdGhlIHJlY3Vyc2l2ZSBjYWxscyByZXN1bHQuCgl4YiA9IGtuYXBzYWNrKGluZGV4ICsgMSwgY2FwYWNpdHkpOyAgLy8gaWYgbm90IHRvIGNob3NlIHRoZSBjdXJyZW50IGl0ZW0uCglpZiAobmV3Y2FwID49IDApICAvLyBpZiBjdXJyZW50IGl0ZW0gZml0cyBpbiB0aGUgY3VycmVudCByZW1haW5pbmcgY2FwYWNpdHk6CgkJeGEgPSBrbmFwc2FjayhpbmRleCArIDEsIG5ld2NhcCkgKyBpdGVtc1tpbmRleF0udmFsdWU7ICAvLyB2YWx1ZSBpZiBjaG9zZSB0aGUgY3VycmVudCBpdGVtLgoJaW50IHJlcyA9IG1heCh4YSwgeGIpOyAgLy8gbWVtb2l6ZSBhbmQgcmV0dXJuIHRoZSBtYXhpbXVtIG9mIGJvdGggcG9zc2libGUgY2hvaWNlcy4KCW1lbW9bY3NdID0gcmVzOwoJcmV0dXJuIHJlczsKfQoKCmludCBtYWluKCkgewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKE5VTEwpOwoKCWludCBTOwoJY2luID4+IFMgPj4gTjsKCWl0ZW1zID0gdmVjdG9yPEl0ZW0+KE4pOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKCQljaW4gPj4gaXRlbXNbaV0uc2l6ZSA+PiBpdGVtc1tpXS52YWx1ZTsKCX0KCWNvdXQgPDwga25hcHNhY2soMCwgUykgPDwgIlxuIjsKCglyZXR1cm4gMDsKfQo=