UVa 624 - CD

// UVa 624 - CD
#include <iostream>
#include <stdio.h>
#include <set>
#include <vector>
using namespace std;

#define integer unsigned long long

void print(int j, vector<integer> v, vector<int> r) {
	if (j > 0) {
		print(r[j], v, r);
		cout << v[j] - v[r[j]] << " ";
	}
}

int main() {
	integer c;
	int n;
	integer t[20];
	while (cin >> c >> n) {
		for (int i = 0; i < n; i++)
			cin >> t[i];
		vector<integer> v;
		vector<int> r;
		set<integer> s;
		int sol = 0;
		v.push_back(0);
		r.push_back(0);
		for (int i = 0; i < n; i++) {
			int stop = v.size();
			for (int j = 0; j < stop; j++) {
				integer a = v[j] + t[i];
				if (a <= c && s.find(a) == s.end()) {
					v.push_back(a);
					s.insert(a);
					r.push_back(j);
					if (a > v[sol])
						sol = v.size() - 1;
				}
			}
		}
		print(sol, v, r);
		cout << "sum:" << v[sol] << endl;
	}
	return 0;
}