program houzihexiangjiao;
var
  s,n,c,i,j,k,t,w,ss,l:longint;
  x,y:array[1..20]of longint;
  bz:array[0..100000,0..100]of boolean;
  biao:array[1..1000000]of boolean;
  jilu:array[1..1000000]of longint;
  dist,data:array[1..1000000]of longint;
procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=jilu[(l+r) div 2];
         repeat
           while jilu[i]<x do
            inc(i);
           while x<jilu[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=jilu[i];
                jilu[i]:=jilu[j];
                jilu[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
  assign (input,'monkeys.in');
  reset (input);
  assign (output,'monkeys.out');
  rewrite (output);
    readln (n,c);
    for i:=1 to c do
      readln(x[i],y[i]);
    readln (k);
    t:=1;
    w:=1;
    data[t]:=0;
    dist[t]:=0;
    for i:=1 to 1000000 do
      biao[i]:=true;
    for i:=0 to 100000 do
      for j:=0 to 100 do
        bz[i,j]:=true;
    bz[0,0]:=false;
    while t<=w do
    begin
      s:=data[t];
      l:=dist[t];
      inc(t);
      for i:=1 to c do
        if s mod (x[i]-1)=0 then
          if bz[s div (x[i]-1)*x[i]+y[i],l+1] then
          begin
            if biao[s div (x[i]-1)*x[i]+y[i]] then
            begin
              inc (ss);
              biao[s div (x[i]-1)*x[i]+y[i]]:=false;
              jilu[ss]:=s div (x[i]-1)*x[i]+y[i];
            end;
            if l+1<n then
            begin
              inc(w);
              data[w]:=s div (x[i]-1)*x[i]+y[i];
              dist[w]:=dist[t]+1
            end
          end
    end;
    if k>ss then
      writeln ('-1')
    else
    begin
      sort(1,ss);
      writeln (jilu[k])
    end;
  close (input);
  close (output)
end.