#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#define ll long long
using namespace std;

int n,m,x[1001],y[1001],K;
bool hash[2000001];

void init()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&K);
}

set <int> S[2],ANS;

void solve()
{
	S[0].insert(0);
	int maxans=1e9;
	for (int T=1;T<=n;T++)
	{
		int o = T & 1;
		S[o].clear();
		for (set<int>::iterator t=S[!o].begin();t!=S[!o].end();t++)
		{
			int a=*t;
			for (int i=1;i<=m;i++)
			if ( a % (x[i]-1) == 0 )
			{
				ll b = (ll)a*(ll)x[i]/(ll)(x[i]-1)+(ll)y[i];
				if (b<=1e9 && b!=0)
				{
					if ( ANS.size()==K && b >=maxans ) ;
					else
					{
						if ( (b<=2000000 && !hash[b]) || ANS.count(b)==0)
						{
							S[o].insert(b);
							if (S[o].size()>K) S[o].erase(--S[o].end());
							ANS.insert(b);
							if (b<=2000000) hash[b]=true;
							if (ANS.size()>K) 
							{
								ANS.erase(--ANS.end());
								maxans=*--ANS.end();
							}
						}
					}
				}
			}
		}
	}
	if (ANS.size()<K) printf("-1\n");
	else printf("%d\n",*--ANS.end());
}

int main()
{
	freopen("monkeys.in","r",stdin);
	freopen("monkeys.out","w",stdout);
	init();
	solve();
	return 0;
}