#include <bits/stdc++.h>
using namespace std;
 
vector<long long> gen(const vector<long long>& v, long long w) {
    vector<long long> s = {0};
    for (long long x : v) {
        vector<long long> t;
        for (long long y : s) {
            long long z = y + x;
            if (z <= w) t.push_back(z);
        }
        s.insert(s.end(), t.begin(), t.end());
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
    }
    return s;
}
 
 int main() {
	freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
    long long w, n;
    cin >> w >> n;
    vector<long long> g(n);
    for (long long i = 0; i < n; ++i) cin >> g[i];
    long long m = n / 2;
    vector<long long> a(g.begin(), g.begin() + m);
    vector<long long> b(g.begin() + m, g.end());
    vector<long long> s1 = gen(a, w);
    vector<long long> s2 = gen(b, w);
    long long ans = 0;
    for (long long x : s1) {
        if (x > w) continue;
        long long y = w - x;
        if (y < 0) continue;
        auto it = upper_bound(s2.begin(), s2.end(), y);
        if (it != s2.begin()) ans = max(ans, x + *(it - 1));
    }
    cout << ans << endl;
    return 0;
}