s51avp1.cpp

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

bool primo[maxn];
int n, m, dp[maxn][110];
vector<int> v, p;

void crivo() // Crivo de Erastótenes para computar todos os primos ate 10^4
{
	memset(primo, 1, sizeof(primo));
	primo[1] = 0;
	primo[0] = 0;

	for(int i = 2; i <= 100; i++)
		for(int j = i * i; j * j < maxn; j += i)
			primo[j] = 0;

	for(int i = 2; i <= n; i++)
		if(primo[i]) p.push_back(i); // lista com todos os primos
}

bool solve(int dinheiro, int obj)
{
	if(dinheiro > n) return 0; // se o dinheiro gasto é maior que o dinheiro total, então é impossível
	
	if(obj == m) // já comprei todos os objetos;
	{
		if(primo[dinheiro]) return true; // caso a quantidade gasta seja prima

		else return false; // caso contrário
	}

	if(dp[dinheiro][obj] != -1) return dp[dinheiro][obj];

	for(auto i : p) // percorro todos os primos e tento comprar uma quantidade prima do objeto atual
	{
		if(i > v[obj]) break;
		if(solve(dinheiro + i*v[obj], obj + 1)) return dp[dinheiro + i*v[obj]][obj + 1] = 1;
		// se eu consigo comprar todos os objetos e gastar uma quantidade	
	}

	return dp[dinheiro][obj] = 0; // caso não seja possível comprar todos e gastar uma quantidade prima
}


int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr); // otimização de entrada
	
	memset(dp, -1, sizeof(dp));
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}

	crivo();

	if(solve(0,0)) cout << "festa dos primos\n";
	
	else cout << "não é a festa dos primos\n";
	
	return 0;
}