#include <bits/stdc++.h> 
using namespace std;
const long long N=47,M=9e6+ 10;
bitset<47> bs;
long long a[N],b[M],c=0; 
int main(){
    freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
	long long n;
	long long m;
	scanf("%lld%d",&m,&n);
	for(long long i=1;i<=n;i++)scanf("%lld",a+i);
	if(n<=23){
		long long ans=0;
		for(long long i=0;i<=(1<<n)-1;i++){
			bs=i;
			long long sum=0;
			for(long long j=0;j<n;j++) if(bs[j])sum +=a[j+1];
			if(sum<=m) ans=max(ans,sum);
		}
		printf("%lld\n",ans);
	}else {
		long long ans=0,cnt=0,mi=n/2;
		for(long long i=0;i<=(1<<mi)-1;i++){
			long long sum=0;
			bs=i;
			for(long long j=0;j<mi;j++){
				if(bs[j])sum +=a[j+1];c++;
				if(sum>m)break;
			}
			if(sum<=m)b[++cnt]=sum;
		}
		sort(b+1,b+cnt+1);
		cnt=unique(b+1,b+cnt+1)-b-1;
		if(b[n]==m){
			cout<<m;
			return 0;
		}
		for(long long i=0;i<=(1<<(n-mi))-1;i++){
			bs=i;
			long long sum=0;
			for(long long j=0;j<(n-mi);j++){
				if(bs[j])sum +=a[j+mi+1];c++;
				if(sum>m)break;
			}
			if(sum<=m){
				long long l=1,r=cnt,p=0;
				while(l<=r){
					long long mid=l+r>> 1;
					if(sum+b[mid]<=m){
						l=mid+1;
                        p=mid;
					}else r=mid-1;
				}
				ans=max(ans,b[p]+sum);
			}
			if(ans==m) break;
		}
		cout<<ans<<"\n";
	}
	return 0;
}