program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  MAXIN = 1000000000;

var
  a: array [1..MAXIN] of byte;
  b: array [1..100] of integer;
  n, m, i, j, a1, sum1, sum: integer;

procedure clean();
var
  i: integer;
begin
  for i := 1 to n do
    a[i] := 0;
  for i := 1 to m do
    a[b[i]] := 1;
end;

begin
  readln(n, m);
  j := 1;

  for i := 1 to m do
  begin
    read(a1);
    b[j] := a1;
    b[j + 1] := a1;
    inc(j, 2);
  end;

  m := m * 2;
  clean();

  sum1 := 0;

  for i := 1 to m do
    sum1 := sum1 + b[i];

  sum := sum1;

  if (sum < n) then
    writeln(-1)
  else
  begin
    i := 0;
    while (i <= n) do
    begin
      for j := 1 to m do
        if (a[i + b[j]] = 0) and (a[i] <> 0) then
          a[i + b[j]] := a[i] + 1;
      inc(i);
    end;
    writeln(a[n]);
  end;

  readln;
  readln;
end.