// AddPrimeToN.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
#include <algorithm>

typedef std::vector<std::int64_t> DType;

//エラトステネスの篩型プライムエンカウンター。

template<class T = std::size_t>
class PrimeEncounterAnother {
public:
	typedef std::vector<bool> PrimeSet;
	typedef T Integer;

	PrimeEncounterAnother() {
		Clear();
	}

	bool Clear() {
		Primes.clear();
		if (Primes.size() == 0) {
			Primes.push_back(true);
			Primes.push_back(true);
			Searched = 1;
		}
		return true;
	}

	bool Search(const Integer& N) {
		if (Searched >= N) return false;
		Integer L = static_cast<Integer>(std::sqrt(N)) + 1;
		Primes.resize(N + 1);
		for (Integer i = 0; i < L; i++) {
			if (Primes[i] == true) continue;
			for (Integer j = (Searched / i) + 1; i*j <= N; j++) {
				if (j <= 1)continue;
				Primes[i*j] = true;
			}
		}
		Searched = N + 1;
		return true;
	}
	Integer IsSearched() {
		return Searched;
	}
	Integer Size() {
		return Primes.size();
	}
	bool operator [](const Integer& Idx) {
		return !Primes[Idx];
	}
protected:
	PrimeSet Primes;
	Integer Searched;
};

bool Rec(DType P, DType D, const std::uint64_t& A, const std::uint64_t& V,const std::uint64_t& LN,DType& R) {
	if (D.size() > LN) return false;
	if (A < V)return false;
	if (A == V) {
		R = D;
		return true;
	}

	for (std::size_t i = 0; i < P.size(); i++) {
		D.push_back(P[i]);
		P.erase(P.begin() + i);
		Rec(P, D, A, V + D.back(), LN, R);
		P.insert(P.begin() + i,D.back());
		D.pop_back();
	}

	return false;
}

DType MakeHoge(std::uint64_t N) {
	PrimeEncounterAnother<std::uint64_t> P;
	DType D;
	P.Search(N);
	for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
		if (P[i] == true)D.push_back(i);
	}

	std::vector<std::vector<std::int64_t>> DP(D.size() + 2);
	for (auto& o : DP) {
		o.resize(N + 2);
	}
	std::vector<std::vector<std::vector<std::int64_t>>> T(D.size() + 2);
	for (auto& o : T) {
		o.resize(N + 2);
	}
	for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;

	for (std::int64_t i = D.size() - 1; i >= 0; i--) {
		for (std::int64_t j = 0; j <= N; j++) {
			if (j < D[i]) {
				DP[i][j] = DP[i + 1][j];
				T[i][j] = T[i + 1][j];
			}
			else {
				if (DP[i + 1][j] > DP[i + 1][j - D[i]] + 1) {
					DP[i][j] = DP[i + 1][j];
					//T[i][j] = T[i + 1][j];
				}
				else {
					DP[i][j] = DP[i + 1][j - D[i]] + 1;
					T[i + 1][j - D[i]].push_back(D[i]);
					T[i][j] = T[i + 1][j - D[i]];
				}
			}
		}
	}
		std::vector<std::int64_t> R = T[0][N];
		std::sort(R.begin(), R.end());

		return R;
	
}

int main()
{
	std::uint64_t N=0;
	auto R=MakeHoge(2018);
	std::cout << R.size() << ": " ;
	for (auto& o: R) {
		N += o;
	}
	std::cout << N<< ": " ;
	for (auto& o : R) {
		std::cout << o << ',';
	}
	std::cout<<std::endl;

    return 0;
}