Knapsack

#include <bits/stdc++.h>

using namespace std;

int main() {
    int s, n;
    cin >> s >> n;
    int w[n];
    for (int i= 0; i < n; ++i) {
        cin >> w[i];
    }

    bool dp[s + 1] = {};
    dp[0] = true;
    int res = 0;

    for (int i = 0; i < n; ++i) {
        for (int x = s; x >= 0; --x) {
            if (dp[x] && x + w[i] <= s) {
                dp[x + w[i]] = true;
                res = max(res, x + w[i]);
            }
        }
    }

    cout << res;
    return 0;
}