/*
优化搜索顺序:将所有物品按重量从大到小排序,每次先搜大的重量
双向dfs:预处理前k件物品能凑出来的重量,排序之后去重,再搜索剩下n-k个物品,选完最后一个物品之
后查预处理的表得小于等于限制m-当前凑出来的重量和的最大能凑出来的重量,更新答案(二分)
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1<<24;//n最大是46,预处理前n/2件物品,最多有1<<23种组合方式
typedef long long ll;//有些方案凑出来的数可能会爆int
int n,m,k;//m为限制,k为预处理数的个数
int w[50],weight[N];//w存每个物品的重量,weight存前k个物品凑出来的每一个重量
int cnt=0;//存对weight里面的数去重之后数的个数
int ans;
void dfs1(int u,int s)//当前在处理哪个数,总和为多少
{
if(u==k)
{
weight[cnt++]=s;
return;
}
if((ll)s+w[u]<=m)
dfs1(u+1,s+w[u]);
dfs1(u+1,s);
}
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(weight[mid]+(ll)s<=m)
l=mid;
else
r=mid-1;
}
if(weight[l]+(ll)s<=m)
ans=max(ans,weight[l]+s);
return;
}
if((ll)s+w[u]<=m)
dfs2(u+1,s+w[u]);
dfs2(u+1,s);
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++)
cin>>w[i];
sort(w,w+n,greater<int>());
k=n/2;
dfs1(0,0);
sort(weight,weight+cnt);
cnt=unique(weight,weight+cnt)-weight;//unique返回去重后最后一个不重复元素的下一个元素的地址,减去weight,得到去重后元素的个数
dfs2(k,0);
cout<<ans;
return 0;
}