记录编号	571820	评测结果	AAAAAAAAET
题目名称	送礼物	最终得分	80
用户昵称	遥时_彼方	是否通过	未通过
代码语言	C++	运行时间	6.283 s
提交时间	2022-06-25 13:33:15	内存使用	126.66 MiB

#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
////////////////////////
const ll N=1e7+50;
ll w,nc;
ll n[51];
ll a[N];
int aj;
ll b[N];
int bj;
ll ans;
inline void sol1()
{
	int mid=(nc>>1)+(nc&1);
	int j;
	rep(i,1,mid)
	{
		j=aj;
		rep(o,0,j)
		{
			a[++aj]=a[o]+n[i];
			if(a[aj]>w) aj--;
		}
	}
	sort(a+1,a+aj+1);
}
ll fin(ll x,int l,int r)
{
	if(l==r) return a[l];
	int mid=(l+r)>>1;
	if(a[mid+1]<=x) return fin(x,mid+1,r);
	else fin(x,l,mid);
}
inline void sol2()
{
	int mid=(nc>>1)+(nc&1);
	int j;
	ll re;
	rep(i,mid+1,nc)
	{
		j=bj;
		rep(o,0,j)
		{
			b[++bj]=b[o]+n[i];
			if(b[bj]>w)
			{
				bj--;
				continue;
			}
			ans=max(ans,b[bj]);
			re=fin(w-b[bj],1,aj);
			if(re+b[bj]>w) continue; 
			ans=max(re+b[bj],ans);
//			if(ans==20) cout<<"A:"<<re<<" "<<b[bj]<<endl;
		}
	}
}
int main()
{
    freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
    cin>>w>>nc;
    rep(i,1,nc) n[i]=read();
    sol1();
    sol2();
    cout<<ans<<endl;
    return 0;
}