package yukicoder; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String[] args){ new Main().solver(); } void solver(){ Scanner sc=new Scanner(System.in); int M=sc.nextInt(); int N=sc.nextInt(); int[] C=new int[N]; for(int i=0;i<N;i++){ C[i]=sc.nextInt(); } // size is 1229 ArrayList<Integer> primeList=primeList(10010); Arrays.sort(C); int[] possible_num=new int[10010]; for(int j=M;j>=0;j--){ for(int i=0;i<N;i++){ if(j+C[i]<=M){ if(possible_num[j+C[i]]>0||j+C[i]==M) possible_num[j]=Math.max(possible_num[j+C[i]]+1,possible_num[j]); } } } long ans=0; long max=0; for(int i=1;i<M;i++){ if(primeList.contains(i)){ ans+=possible_num[i]; // System.out.println(i+" "+possible_num[i]); } } for(int i=0;i<M;i++){ max=Math.max(max, possible_num[i]); } ans+=max; System.out.println(ans); } boolean[] isPrimeArray(int max){ boolean[] isPrime=new boolean[max+1]; Arrays.fill(isPrime, true); isPrime[0]=isPrime[1]=false; for(int i=2;i*i<=max;i++){ if(isPrime[i]){ for(int j=2;j*i<=max;j++){ isPrime[j*i]=false; } } } return isPrime; } /* * max以下の素数のリストを返す */ ArrayList<Integer> primeList(int max){ boolean[] isPrime=isPrimeArray(max); ArrayList<Integer> primeList=new ArrayList<Integer>(); for(int i=2;i<=max;i++){ if(isPrime[i]){ primeList.add(i); } } return primeList; } /* * numをprimeListの素数をもとに素因数分解し、因数を * ArrayList<Factor>の形で返す。1は含まれない。 * primeListにはnumの平方根以下の素数が含まれていなければならない。 * */ ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList,long num){ ArrayList<Factor> ret=new ArrayList<Factor>(); for(int p:primeList){ int exp=0; while(num%p==0){ num/=p; exp++; } if(exp>0)ret.add(new Factor(p,exp)); } if(num>1)ret.add(new Factor(num,1)); return ret; } class Factor{ long base,exp; Factor(long base,long exp){ this.base=base; this.exp=exp; } } /* * 戻り値:約数の和 * verified:yukicoder No.278 */ long sum_d(ArrayList<Factor> fs){ long sum=1; for(Factor f:fs){ sum*=Long.parseLong((BigInteger.ONE.subtract(pow_big(f.base,f.exp+1))).divide(BigInteger.ONE.subtract(BigInteger.valueOf(f.base))).toString()); } return sum; } BigInteger pow_big(long a,long n){ BigInteger A=new BigInteger(String.valueOf(a)); BigInteger ans=BigInteger.ONE; while(n>=1){ if(n%2==0){ A=A.multiply(A); n/=2; }else if(n%2==1){ ans=ans.multiply(A); n--; } } return ans; } /*Verified:yukicoder377 * Eulerのφ関数(Euler's totient function) 1からnまでの自然数のうちnと互いに素なものの個数を数える。 * φ(mn)=φ(m)φ(n) (gcd(m,n)=1) なぜならば、chinese reminder theoremより、 a mod mnと * (a mod n)と(b mod m)は全単射。 φ(p^k)=p^k-p^(k-1)=p^k(1-1/p) * よってφ(p^k*q^k)=n(1-1/p)(1-1/q)という風にできる。 */ long totient_function(ArrayList<Factor> f, long n) { long ret = n; for (int i = 0; i < f.size(); i++) { ret = ret - ret / f.get(i).base; } return ret; } // nの約数を列挙。1とnを含む。 ArrayList<Long> enum_div(ArrayList<Factor> f) { ArrayList<Long> ret = new ArrayList<Long>(); ret.add(1L); for (int i = 0; i < f.size(); i++) { long a = 1; int n = ret.size(); for (int j = 0; j < f.get(i).exp; j++) { a *= f.get(i).base; for (int k = 0; k < n; k++) { ret.add(ret.get(k) * a); } } } return ret; } }