//双向搜索,先将一部分的礼物能出现的组合打表
//对于后一部分,搜索到一种组合后,再在前一部分的组合中找合适的组合,两个组合加起来重量<=w,取max就是答案
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 46+2;
int ans, n, pre, w;
int g[N];
int num[1<<(N/2)], cnt;
void dfs1(int m, int k){
if(k==pre){
num[cnt++] = m;
return ;
}
dfs1(m, k+1);
if((ll)m+g[k]<=w) dfs1(m+g[k], k+1);
return ;
}
void dfs2(int m, int p){
if(p>=n){
//这里注意一下使用 upper_bound 和 lower_bound 的区别
int i = upper_bound(num, num+cnt, w-m) - num - 1;
//int i = lower_bound(num, num+cnt, w-m) - num;
//if(num[i]>(w-m) || i==cnt) i--;
ans = max(ans, m+num[i]);
return ;
}
dfs2(m, p+1);
if((ll)m+g[p]<=w) dfs2(m+g[p], p+1);
return ;
}
int main(){
scanf("%d%d", &w, &n);
for(int i=0; i<n; i++) scanf("%d", &g[i]);
sort(g, g+n, greater<int>());
pre = n/2 + 2;
dfs1(0, 0);
sort(num, num+cnt);
cnt = unique(num, num+cnt) - num;
dfs2(0, pre);
cout<< ans<< endl;
return 0;
}