#include <bits/stdc++.h>
using namespace std;
const int N = 50;
#define int long long
int ans, n, m, k, w;
int a[N], res[(int) 1e7 + 10], tot;


// 搜第一半
void dfs(int u, int sum) {
	if (u > k) {
		res[++tot] = sum;
		return ;
	}
	// 对于当前物品，不拿
	dfs(u + 1, sum);
	// 拿
	if (sum + a[u] <= m)
		dfs(u + 1, sum + a[u]);
}

// 搜索另一半
void dfs1(int u, int sum) {
	if (u > n) {
		int t = m - sum;
		// 在之前的搜索结果里面找
		int it = upper_bound(res + 1, res + 1 + tot, t) - res;
		ans = max(ans, sum + res[it - 1]);
		return ;
	}
	// 对于当前物品，不拿
	dfs1(u + 1, sum);
	// 拿
	if (sum + a[u] <= m)
		dfs1(u + 1, sum + a[u]);
}

signed main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	k = n / 2;
	dfs(1, 0);
	sort(res + 1, res + 1 + tot);
	dfs1(k + 1, 0);
	cout << ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n, path[N] = {1};

// 序列的最大长度为 depth
// 当前的深度为 u
bool dfs(int u, int depth) {
	if (u == depth) {
		return path[u - 1] == n;
	}
	// 凑出 u 这个位置的数字，
	for (int i = u-1; i>=0; i--)
		for (int j = i; j >=0 ; j--) {
			int t = path[i] + path[j];
			if (t < path[u - 1]) 
				continue;
			if (t <= n) {
				path[u] = t;
				if (dfs(u + 1, depth))
					return 1;
			}
		}
	return 0;
}

int main() {
	while (cin >> n, n) {
		for (int depth = 1; ; depth++) {
			if (dfs(1, depth) == 0)
				continue;
			for (int i = 0; i < depth ; i ++)
				cout << path[i] << " ";
			cout << endl;
			break;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};

int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};

int n, m;
char a[N][N];
bool vis[N][N];
int res;

void dfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue;
		if (a[nx][ny] == '.')
			continue;
		if (vis[nx][ny])
			continue;
		vis[nx][ny] = 1;
		dfs(nx, ny);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	// 从每一个点去搜索
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (vis[i][j])
				continue;
			if (a[i][j] == '.')
				continue;
			res++; // 有连通块了
			vis[i][j] = 1;
			dfs(i, j);
		}
	cout << res;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int dx[] = {0, -1, 0, 1};

int dy[] = {-1, 0, 1, 0};
int n, m, a[N][N];
bool vis[N][N];
pair<int, int> res[N * N];
int sx, sy, fx, fy;
bool flg = 1;

// stp 代表走第几步
void dfs(int x, int y, int stp) {
	res[stp].first = x, res[stp].second = y;
	// 走到了结束
	if (x == fx && y == fy) {
		flg = 0;
		printf("(%d,%d)", res[1].first, res[1].second);
		for (int i = 2; i <= stp; i++)
			printf("->(%d,%d)", res[i].first, res[i].second);
		puts("");
		return ;
	}
	//  拓展
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx > n  || ny < 1 || ny > m)
			continue;
		if (a[nx][ny] == 0)
			continue;
		if (vis[nx][ny])
			continue;
		vis[nx][ny] = 1;
		dfs(nx, ny, stp + 1);
		vis[nx][ny] = 0;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	cin >> sx >> sy >> fx >> fy;
	if (a[sx][sy] == 0 || a[fx][fy] == 0) {
		cout << -1;
		return 0;
	}
	vis[sx][sy] = 1;
	dfs(sx, sy, 1);
	if (flg)
		cout << -1;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};
int n, a[N][N], res;
bool vis[N][N];

void dfs(int x, int y) {
	if (a[x][y] == 2) { // 找到宝藏
		res++;
		return ;
	}
	// 拓展
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > n)
			continue;
		if (a[nx][ny] == 1)
			continue;
		if (vis[nx][ny])
			continue;
		vis[nx][ny] = 1;
		dfs(nx, ny);
		vis[nx][ny] = 0;
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	vis[1][1] = 1;
	dfs(1, 1);
	cout << res;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};
int n, m, ans = 1e9;
char a[N][N];
bool vis[N][N];
int  sx, sy, fx, fy;

void dfs(int x, int y, int t) {
	// 结束条件
	if (x == fx && y == fy) {
		ans = min(ans, t);
		return ;
	}
	// 拓展其他点
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 越界
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue;
		// 不能走
		if (a[nx][ny] == '#')
			continue;
		// 走过
		if (vis[nx][ny])
			continue;
		vis[nx][ny] = 1;
		if (a[nx][ny] >= '0' && a[nx][ny] <= '9')
			dfs(nx, ny, t + a[nx][ny] - '0' + 1 );
		else
			dfs(nx, ny, t + 1);  // +1 走到下一个格
		vis[nx][ny] = 0; // 回溯
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'Z')
				sx = i, sy = j;
			if (a[i][j] == 'W')
				fx = i, fy = j;
		}
	vis[sx][sy] = 1;
	dfs(sx, sy, 0);
	if (ans == 1e9)
		puts("IMPOSSIBLE");
	else
		cout << ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

// 有的题目规定了怎么走
int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};
int n, m;
char a[N][N];

bool vis[N][N]; // 标记数组，标记某个点是否能走
bool flg; // 标记能否走通

// 本质是递归
void dfs(int x, int y) {
	// 结束条件
	if (x == n && y == m) {
		flg = 1;
		return ;
	}
	// 没有到最后
	// 从当前点扩展
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 1. 越界
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue;
		// 2. 能否走
		if (a[nx][ny] == '#')
			continue;
		// 3. 是否走过
		if (vis[nx][ny])
			continue;
		// 到这里，证明当前点没有走过
		vis[nx][ny] = 1;
		dfs(nx, ny);  // dfs 当前点
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	vis[1][1] = 1;
	dfs(1, 1);   // dfs dep first search  深度优先搜索
	if (flg)
		cout << "YES";
	else
		cout << "NO";
	return 0;
}