#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

struct Node
{
	int x,y;
}A[31];

int N,C,K;
multiset<int>Tree[2];
multiset<int>::iterator it;

int main()
{
	freopen("monkeys.in","r",stdin);
	freopen("monkeys.out","w",stdout);
	scanf("%d%d",&N,&C);
	for(int i=1;i<=C;i++)
		scanf("%d%d",&A[i].x,&A[i].y);
	Tree[0].insert(0);
	for(int i=1;i<=N;i++)
	{
		int k=i&1;
		Tree[k].clear();
		for(it=Tree[!k].begin();it!=Tree[!k].end();it++)
			for(int j=1;j<=C;j++)
				if(!(*it%(A[j].x-1)))
					Tree[k].insert(*it/(A[j].x-1)*A[j].x+A[j].y);
	}
	scanf("%d",&K);
	if(Tree[N&1].size()<K)
		printf("-1\n");
	else
	{
		K=N-K;
		it=Tree[N&1].begin();
		for(int i=1;i<=K;i++,it++);
		printf("%d\n",*it);
	}
	return 0;
}