CPH page 114

#include <bits/stdc++.h>

using namespace std;

int main() {
    int X, N;
    cin >> X >> N;
    vector < int > w(N);
    for(int& x : w)
        cin >> x;
    pair < int , int > dp[1 << N];
    dp[0] = {1, 0};
    for(int s = 1; s < (1 << N); ++s) {
        dp[s] = {N + 1, 0};
        for(int p = 0; p < N; ++p)
            if(s & (1 << p)) {
                auto opt = dp[s ^ (1 << p)];
                if(opt.second + w[p] <= X)
                    opt.second += w[p];
                else {
                    ++opt.first;
                    opt.second = w[p];
                }
                dp[s] = min(dp[s], opt);
            }
    }
    cout << dp[(1 << N) - 1].first;
}