折半搜索

#define __WIN64__
#if __cplusplus >= 201103L
#define PROJECT_CPP11 1
#else
#error "CPlusPlus < 201103L"
#endif
#ifdef __linux__
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#endif
/*
@ May.4
@ problem from: MQCOJ_Contest
@ cc.cc17o2
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using s64 = signed long long;
using u32 = unsigned int;
using u64 = unsigned long long;
#define lod long double
#define PII pair<int,int>
#ifdef __linux__
#define gc getchar
#define pc putchar
#endif
#define rep(i,x,n) for(int i = x;i <= n; ++i)
#define rep2(i,n) for(int i = n;i >= n;--i)
#define debug(x) cout << #x << " : " << x << "\n";
#define debug2(x,y) cout << #x << " : " << x << " " << #y << " : " << y << "\n";

/*CPP_Name*/
namespace project::config {
	std::tuple<int, std::string, bool> get_app_info() {
		return {100, "送礼物", 0 };
	}
	template <typename T>
	T sum(constexpr std::vector<T> &vec) {
		return std::accumulate(vec.begin(), vec.end(), T{ });
	}
}

/*---QuickIO---*/
namespace Quick {
	inline void Input_Output(void) {
		cin.tie(nullptr)->sync_with_stdio(false);
	}
}

/*---Code---*/
namespace Cplus17 {
	constexpr ll N = 50;
	int 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";
	}
}

/*---Freopen---*/
auto Freopen = [](string s) -> void {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
};

/*---Main---*/
signed main(void) noexcept {
	Quick::Input_Output();
#ifdef __linux__
	Freopen;
#endif
	setvbuf(stdin, NULL, _IOFBF, 1 << 25);
	setvbuf(stdout, NULL, _IOFBF, 1 << 25);
	/*cout<<fixed<<setprecision(10);*/
	int T_ = 1;
	/*cin >> T_;*/
	while (T_--)
		Cplus17::NaCl();
	return 0;
}