/*
思路
1. 以物品重量进行排序
2. 将前k件物品可以凑出的所有重量打表，排序&判重
3. 搜索剩下的N-K件物品的选择方式，在表中二分出不超过W的最大值
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 46;

int n, m, k;
int w[N];
int weights[1 << 25], cnt = 1;
int res;

void dfs1(int u, int s) {
    if(u == k) {
        weights[cnt++] = s;
        return ;
    }
    //不选择第u个物品
    dfs1(u+1, s);
    if((LL)s + w[u] <= m) 
        dfs1(u+1, s+w[u]);
}

void dfs2(int u, int s) {
    if(u == n) {
        int l = 0, r = cnt - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(weights[mid] + (LL)s <= m) l = mid;
            else r = mid - 1;
        }
        res = max(res, weights[l] + s);
        return ;
    }

    dfs2(u+1, s);
    if((LL)s + w[u] <= m) dfs2(u+1, s + w[u]);
}

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

    sort(w, w+n);
    reverse(w,w+n);

    k = min(n/2 + 2, n);
    dfs1(0, 0);
    //当前枚举到第多少个物品，可以凑出的物品价值

    sort(weights, weights+cnt);
    cnt = unique(weights, weights + cnt) - weights;

    dfs2(k, 0);

    cout << res << endl;
    return 0;
}