折半搜索

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,x,n) for(int i = x;i <= n; ++i)

namespace Online
{
	constexpr ll N = 50;
	ll n, m, k;
	ll Answer, cnt;
	ll a[N];
	ll Weight[1 << 24];
	inline void Depth_First_Search1(int u, ll sum)
	{
		if (u > k) {
			Weight[++cnt] = sum;
			return ;
		}
		Depth_First_Search1 (u + 1, sum);
		if (sum + a[u] <= m)
			Depth_First_Search1 (u + 1, sum + a[u]);
	}
	inline void Depth_First_Search2 (int u, ll sum)
	{
		if (u > n) {
			int Left = 1, Right = cnt;
			while (Left < Right) {
				int Mid = Left + Right + 1 >> 1;
				if (Weight[Mid] + sum <= m)
					Left = Mid;
				else
					Right = Mid - 1;
			}
			Answer = max (Answer, Weight[Left] + sum);
			return ;
		}
		Depth_First_Search2 (u + 1, sum);
		if (sum + a[u] <= m)
			Depth_First_Search2 (u + 1, sum + a[u]);
	}
	inline void NaCl(void)
	{
		cin >> m >> n;
		rep(i, 1, n)
		cin >> a[i];
		sort (a + 1, a + 1 + n, greater <int> ()), k = n / 2;
		Depth_First_Search1 (1, 0), sort (Weight + 1, Weight + 1 + cnt);
		cnt = unique (Weight + 1, Weight + 1 + cnt) - Weight - 1, Depth_First_Search2 (k + 1, 0);
		cout << Answer << "\n";
	}
}

auto main(void) -> signed
{
	cin.tie(nullptr)->sync_with_stdio(false);
	Online::NaCl();
}