Program Monkeys;
Const
	inf = 'monkeys.in';
	ouf = 'monkeys.out';
Var
	n,m,i,now,ans,num,k : longint;
	x,y,en,sy : array [0..200] of longint;
        aa : array [0..10000] of longint;

Function V(x,y : longint) : boolean;
	Var
		i : longint;
	Begin
		for i := 1 to y do
		 if en[i]=x then exit(false);
		exit(true);
	End;

Procedure Init;
	Var
		i : longint;
	Begin
		readln(n,m);
		now := 1;
		en[now] := 0;
		for i := 1 to m do
		  begin
			readln(x[i],y[i]);
			if v(y[i],now) then begin
				inc(now);
				en[now] := y[i];
					end;
		  end;
                readln(k);
	End;

Procedure Jilu(x : longint);
	Begin
               { for i := 1 to ans do
                 if aa[i]=x then exit; }
                if x=0 then exit;
                inc(ans);
		aa[ans] := x;
	End;

Procedure Work(k : longint);
	Var
		i,tmp : longint;
	Begin
		if k=1 then begin Jilu(sy[1]); exit; end;
		tmp := sy[k];
		for i := 1 to m do {k-1 way}
		  begin
			if (tmp mod (x[i]-1))<>0 then continue;
			sy[k-1] := x[i]*(tmp div (x[i]-1)) +y[i];
                        Work(k-1);
                        sy[k-1] := tmp;
		  end;
	End;

Procedure Qsort(l,r : longint);
        Var
                i,j,mid,tmp : longint;
        Begin
                i := l; j := r; mid := aa[(l+r) div 2];
                repeat
                  while aa[i]<mid do inc(i);
                  while aa[j]>mid do dec(j);
                  if i<=j then
                   begin
                       tmp := aa[i];
                       aa[i] := aa[j];
                       aa[j] := tmp;
                       inc(i); dec(j);
                   end;
                until j<i;
                if l<j then Qsort(l,j);
                if i<r then Qsort(i,r);
        End;

Begin
	Assign(input,inf); Reset(input);
	Assign(output,ouf); Rewrite(output);

	Init;

	for i := 1 to now do
	  begin
		sy[n] := en[i];
		work(n);
	  end;

        Qsort(1,ans);

        num := 0;
        for i := 1 to ans do
         if aa[i]<>aa[i-1] then
          begin
           inc(num);
           if num=k then begin writeln(aa[i]); break; end;
          end;
        if num<k then writeln(-1);

	Close(input); Close(output);
End.