记录编号	26811	评测结果	ATWTTTTTTWATTT
题目名称	猴子和香蕉	最终得分	14
用户昵称	Yoghurt	是否通过	未通过
代码语言	Pascal	运行时间	12.345 s
提交时间	2011-07-27 14:41:37	内存使用	95.49 MiB

program monkeys;
const
        filename='monkeys';
        maxb=2000000;
        maxn=5000000;
type
        xx=record
                flag:boolean;
                sy,step:longint;
        end;
var
        x,y:array[0..maxn] of longint;
        que:array[0..maxn] of xx;
        n,m,q,tot:longint;

procedure init;
var
        i:longint;
begin
        readln(n,m);
        for i:=1 to m do
                readln(x[i],y[i]);
        readln(q);
end;

function check(b0:longint):boolean;
var
        head,tail,i:longint;
begin
        head:=0; tail:=1;
        que[tail].flag:=true;
        que[tail].sy:=b0;
        que[tail].step:=0;
        while head<tail do
        begin
                inc(head);
                for i:=1 to m do
                begin
                        if que[head].sy<y[i] then continue;
                        if (que[head].sy-y[i]) mod x[i]<>0 then continue;
                        inc(tail);
                        que[tail].step:=que[head].step+1;
                        que[tail].sy:=que[head].sy-y[i]-(que[head].sy-y[i]) div x[i];
                        if ((que[tail].step=n)and(que[tail].sy=0)) then exit(true);
                        if ((que[tail].step=n-1)and(que[tail].sy=0)) then exit(true);
                end;
        end;
        exit(false);
end;

procedure solve;
var
        i:longint;
begin
        tot:=0;
        for i:=1 to maxb do
                if check(i) then
                begin
                        inc(tot);
                        if tot=q then
                        begin
                                writeln(i);
                                exit;
                        end;
                end;
        writeln(-1);
end;

begin
        assign(input,filename+'.in'); reset(input);
        assign(output,filename+'.out'); rewrite(output);

        init;
        solve;

        close(input); close(output);
end.