var
c,h,i,j,k,max:longint;
f:array[0..100000]of boolean;
begin
assign(input,'hay4sale.in');reset(input);
assign(output,'hay4sale.out');rewrite(output);
fillchar(f,sizeof(f),false);
read(c,h);
f[0]:=true;
max:=0;
for i:=1 to h do
 begin
  readln;
  read(k);
  for j:=max downto 0 do
   if f[j] then
    begin
     f[j+k]:=true;
     if j+k>max then max:=j+k;
    end;
  if max>c then max:=c;
 end;
if max<=c then write(max)
else
 for i:=c downto 0 do
  if f[i] then
   begin
    write(i);
    break;
   end;

close(input);
close(output);
end.