记录编号	26820	评测结果	AAAAAAAEEAAEEE
题目名称	猴子和香蕉	最终得分	64
用户昵称	老虎小飞	是否通过	未通过
代码语言	Pascal	运行时间	0.014 s
提交时间	2011-07-27 15:32:20	内存使用	57.34 MiB

var
d,a,w:array[0..5000000]of longint;
n,c,k,i,j,t,h,max:longint;
x,y:array[0..20]of longint;

procedure up(x:longint);
var
x0,tmp:longint;
begin
    if x=1 then exit;
    x0:=x div 2;
    if (a[d[x]]<a[d[x0]]) or ((a[d[x]]=a[d[x0]])and(d[x]<d[x0])) then begin
        tmp:=d[x];d[x]:=d[x0];d[x0]:=tmp;
        tmp:=w[d[x]];w[d[x]]:=w[d[x0]];w[d[x0]]:=tmp;
        up(x0);
    end;
end;

procedure down(x:longint);
var
c,tmp:longint;
begin
    c:=0;
    if x*2+1<=t then c:=x*2+1;
    if x*2<=t then begin
        if c=0 then c:=x*2
        else begin
            if (a[d[c]]>a[d[x*2]]) or ((a[d[x]]=a[d[c]])and(d[x*2]<d[c])) then c:=x*2;
        end;
    end;
    if c<>0 then
        if (a[d[c]]<a[d[x]]) or ((a[d[x]]=a[d[c]])and(d[c]<d[x])) then begin
        tmp:=d[x];d[x]:=d[c];d[c]:=tmp;
        tmp:=w[d[x]];w[d[x]]:=w[d[c]];w[d[c]]:=tmp;
        up(c);
    end;
end;

procedure bfs;
var
i,tmp,m:longint;
begin
    for i:=1 to c do begin
        m:=y[i];
        if w[m]=0 then begin
            inc(t);
            d[t]:=m;
            a[m]:=1;
            w[m]:=t;
            inc(max);
            up(t);
        end;
    end;
    while (t<>0)and(max<k+c*c) do begin
        m:=d[1];
        d[1]:=d[t];w[m]:=0; w[d[1]]:=1;
        dec(t);
        if t>0 then down(1);
        if a[m]<n then
            for i:=1 to c do begin
                if m mod (x[i]-1)=0 then begin
                    tmp:=m div (x[i]-1)*x[i]+y[i];
                    if (a[tmp]=0)or(a[tmp]>a[m]+1) then begin
                        if a[tmp]=0 then inc(max);
                        a[tmp]:=a[m]+1;
                        if w[tmp]=0 then begin
                            inc(t);
                            w[tmp]:=t;
                            d[t]:=tmp;
                        end;
                        up(w[tmp]);
                    end;
                end;
            end;
    end;
end;

begin
    assign(input,'monkeys.in');reset(input);
    assign(output,'monkeys.out');rewrite(output);
    read(n,c);
    for i:=1 to c do read(x[i],y[i]);
    read(k);
    bfs;
    j:=0;t:=-1;
    if max<k then writeln('-1')
    else begin
        i:=1;
        while k>1 do begin
            while a[i]=0 do inc(i);
            inc(i);
            dec(k);
        end;
        while a[i]=0 do inc(i);
        writeln(i);
    end;
    close(input);close(output);
end.