#include <cstdio>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int maxc=21;
struct Choice
{
	int x,y;
};
Choice P[maxc];
int n,e,K;
void init()
{
	scanf("%d%d",&n,&e);
	for (int i=1;i<=e;++i)
		scanf("%d%d",&P[i].x,&P[i].y);
	scanf("%d",&K);
}
struct Cmp
{
	bool operator()(const int &a,const int &b)const
	{return a>b;}
};
int SUM;
priority_queue<int,vector<int>,Cmp> q;
map<int,int> m;
void slove()
{
	q.push(0);
	m[0]=0;
	int key,tmp,dep;
	while (!q.empty())
	{
		tmp=q.top();q.pop();
		dep=m[tmp];
		if (dep<=n)
		{
			if (++SUM>K) 
			{
				printf("%d\n",tmp);
				return;
			}
			if (dep==n) continue;
		}
		for (int i=1;i<=e;++i)
		{
			if (tmp%(P[i].x-1)!=0) continue;
			key=tmp/(P[i].x-1)*P[i].x+P[i].y;
			if (key>1e9) continue;
			if (m.find(key)==m.end())
			{
				m[key]=dep+1;
				q.push(key);
			}else m[key]=min(m[key],dep+1);
		}
	}
	printf("-1\n");
}
int main()
{
freopen("monkeys.in","r",stdin);
freopen("monkeys.out","w",stdout);
	init();
	slove();
	return 0;
}