#include "bits/stdc++.h"

// マクロ群
#define REP(i,n) for(int i=0;i<n;++i)
#define REP2(i,a,b) for (int i=(a);i<(b);++i)
#define rep(n) REP(i,n)
#define SF(f,v) scanf(f,v)
#define PF(f,v) printf(f,v)

using namespace std;

static vector<bool> PrimeFLG;

void MakePrimeFLG(int period)
{
	// 初期化
	PrimeFLG = vector<bool>(period + 1, true);
	PrimeFLG[0] = false;
	PrimeFLG[1] = false;

	//// エラトステネスの篩を使って素数ではない物を更新する

	for (int i = 2; i * i < period; i++)	// √priode　まで繰り返す
		if (PrimeFLG[i] == true)	// 素数の時だけ
			for (int j = i * i; j < period; j += i)	// i を軸に倍々ループ
				PrimeFLG[j] = false;	// i からなるすべての倍数は素数ではない
}

void Slove()
{
	int M, N;

	SF("%d", &M);	// 初期所持金
	SF("%d", &N);	// カップ麺の種類
	vector<int> C(N);
	REP(n, N) SF("%d", &C[n]);	// 種類ごとの価格

	sort(C.begin(), C.end());	// 小さい順に並べ替え

	// 素数のフラグリストを作る
	MakePrimeFLG(M);

	// 金額分の要素を持ったリストを作成する（-1で初期化）
	vector<int> dp = vector<int>(M + 1, -1);

	// 残額をキーとして、その残額になったときに、何個のカップ麺を買えたかをリストに記憶する
	dp[M] = 0;
	for (int money = M; money >= 0; --money)
	{
		if (dp[money] <= -1) continue;

		for (int kind = 0; kind < N; ++kind)
		{
			if (money - C[kind] > -1)
			{
				dp[money - C[kind]] = dp[money - C[kind]] > dp[money] + 1
									? dp[money - C[kind]]
									: dp[money] + 1;
			}
			else break;
		}
	}

	int ans = 0;

	// 一番多く買えた個数を結果に対して加算
	ans += *max_element(dp.begin(), dp.end());

	// 素数の残額キーに記憶された購入個数分はノーリスクで
	// 手に入ったこととなるため、その分を結果に対して加算
	REP(m, M) if (dp[m] > -1 && PrimeFLG[m] == true) ans += dp[m];

	/*REP(m, M) if (dp[m] != -1)
	{
		PF("%4d :", m);
		PF("%d\n", dp[m]);
	}

	PF("__%d\n", ans);*/


	PF("%d", ans);
}

int main()
{
	Slove();
	return 0;
}