#include <bits/stdc++.h>
using namespace std;
const int N=45+5;
typedef long long ll;
const ll inf=0x7fffffff;
int n;
ll g[N],w,ans=0;
ll p[N]={0};
bool cmp(ll x,ll y){
    return x>y;
}
void dfs(int pt,ll num){
    if (num>w)return ;
    if (pt==n/2+1){
        p[++p[0]]=num;
        return ;
    }
    dfs(pt+1,num);
    dfs(pt+1,num+g[pt]);
    return ;
}
void findsum(ll t){
    int l=1,r=p[0]+1;
    while(l<r){
        int mid=(l+r)/2;
        if (p[mid]>t)r=mid;
        else l=mid+1;
    }
    ans=max(ans,w-t+p[l-1]);
    return ;
}
void dfs2(int pt,ll num){
    if (num>w)return ;
    if (pt==n+1){
        findsum(w-num);
        return ;
    }
    dfs2(pt+1,num);
    dfs2(pt+1,num+g[pt]);
    return ;
}
int main(){
    freopen ("giftgiving.in","r",stdin);
    freopen ("giftgiving.out","w",stdout);
    scanf("%lld%d",&w,&n);
    for (int i=1;i<=n;i++){
        scanf("%lld",&g[i]);
    }
    sort(g+1,g+n+1,cmp);
    dfs(1,0);
    sort(p+1,p+p[0]+1);
    int q=0;
    for (int i=1;i<=p[0];i++){
        if (p[i]==p[i-1])q++;
        else p[i-q]=p[i];
    }
    p[0]-=q;
    p[++p[0]]=inf;
    dfs2(n/2+1,0);
    printf("%lld\n",ans);
    return 0;
}