/*
UID:cheepok
PID:monkeys
*/

#include<stdio.h>
#include<set>

using namespace std;

typedef long long Int;

Int n,m,x[21],y[21];

set <Int> s[2],S;

set <Int> :: iterator it;

bool flag[100000000];

int main()
{
	freopen("monkeys.in","r",stdin);
	freopen("monkeys.out","w",stdout);
	Int i,j,k,tmp,tmp1;
	scanf("%I64d%I64d",&n,&m);s[0].insert(0);
	for(i=1;i<=m;i++)scanf("%I64d%I64d",&x[i],&y[i]);
	for(i=1;i<=n;i++)
	{
		k=i&1;s[k].clear();
		for(it=s[!k].begin();it!=s[!k].end();it++)
		{
			tmp=*it;
			for(j=1;j<=m;j++)
			{
				if(tmp%(x[j]-1)==0)
				{
					tmp1=tmp/(x[j]-1)*x[j]+y[j];
					if(tmp1>1000000000)continue;
					if(tmp1<100000000){
					if(flag[tmp1])continue;
					else flag[tmp1]=true;}
					s[k].insert(tmp1);
					S.insert(tmp1);
				}
			}
		}
	}
	scanf("%I64d",&k);
	if(S.size()<k)printf("-1\n");
	else
	{
		it=S.begin();
		for(i=1;i<k;i++)it++;
		printf("%I64d\n",*it);
	}
	return 0;
}