program monkeys;
const
  maxn=50000000;
var
  a:array[0..maxn] of integer;
  x,y:array[0..30] of longint;
  n,c,i,j,k,k1,p,maxnum:longint;
  flag:boolean;
  
begin
  assign(input,'monkeys.in');
  reset(input);
  assign(output,'monkeys.out');
  rewrite(output);
  
  readln(n,c);
  maxnum:=0;
  for i:=1 to c do
  begin
    readln(x[i],y[i]);
    a[y[i]]:=1;
    if y[i]>maxnum then maxnum:=y[i];
  end;
  readln(k);
  
  k1:=0;
  i:=0;
  flag:=false;
  while (i<=maxnum) and (k1<k) do
  begin
    i:=i+1;
    if a[i]>0 then
    begin
      k1:=k1+1;
      if k1=k then
      begin
        flag:=true;
        writeln(i);
        break;
      end;
      if a[i]<n then
        for j:=1 to c do
          if i mod (x[j]-1)=0 then
            if (maxn-y[j])/x[j]>(i div (x[j]-1)) then
            begin
              p:=(i div (x[j]-1))*x[j]+y[j];
              if p>maxnum then maxnum:=p;
              if (a[p]=0) or (a[i]+1<a[p]) then a[p]:=a[i]+1;
            end;
    end;
  end;
  if not flag then writeln(-1);
  
  close(input);
  close(output);
end.