#include <cstdio>
#include <cstdlib>
#include <set>
#include <utility>
#define MAXN 101
#define fst first
#define snd second
using namespace std;
typedef set<int> SET;
pair<int,int> ban[21];
SET Set,tmp[2];
SET::iterator it,iter;
int N,C,K;

inline void init()
{
	scanf("%d %d\n",&N,&C);
	for(int i=1;i<=C;i++) scanf("%d %d\n",&ban[i].snd,&ban[i].fst);
	scanf("%d\n",&K); int x;
	for(int i=1;i<=C;i++) {Set.insert(ban[i].fst);tmp[0].insert(ban[i].fst);}
	for(int i=0;i<N-1;i++)
	{
		for(it=tmp[i&1].begin();it!=tmp[i&1].end();it++)
		{
			x=*it; for(int j=1;j<=C;j++)
			{
				if(x%(ban[j].snd-1)!=0) continue;
				Set.insert(x/(ban[j].snd-1)*ban[j].snd+ban[j].fst);
				tmp[(i+1)&1].insert(x/(ban[j].snd-1)*ban[j].snd+ban[j].fst);
			}
		} tmp[i&1].clear();
	}
}

int main()
{
	freopen("monkeys.in","r",stdin);
	freopen("monkeys.out","w",stdout);
	init(); int i;
	//for(iter=Set.begin();iter!=Set.end();iter++) 
	//printf("%d ",*iter);
	//printf("\n");
	if(K>Set.size()) {printf("-1\n"); return 0;}
	for(iter=Set.begin(),i=2;i<=K;i++,iter++); printf("%d\n",*iter);
	return 0;
}