#include <cstdio>
#include <set>
#include <vector>
#include <queue>
using namespace std;

#define pb push_back
#define mp make_pair
const int MAXC=25;
typedef pair<int,int> Pair;

int N,K,C;
int x[MAXC],y[MAXC];
set<Pair> q;
set<int> hash;

void solve()
{
	q.insert(mp(0,0));
	Pair now;
	int tot=-1;
	while(q.size())
	{
		now=*q.begin();q.erase(q.begin());
		tot++;
		if (tot==K)
			break;
		if (now.second<N)
		{
			for(int i=0;i<C;i++)
				if (now.first%(x[i]-1)==0)
				{
					Pair expand(now.first/(x[i]-1)*x[i]+y[i],now.second+1);
					if (hash.count(expand.first)==0)
					{
						q.insert(expand);
						if ((int)q.size()>K)
							q.erase(--q.end());
						if (q.count(expand)!=0)
							hash.insert(expand.first);
					}
				}
		}
	}
	if (tot==K)
		printf("%d\n",now.first);
	else
		printf("-1\n");
}

int main()
{
	freopen("monkeys.in","r",stdin);
	freopen("monkeys.out","w",stdout);
	scanf("%d%d",&N,&C);
	for(int i=0;i<C;i++)
		scanf("%d%d",x+i,y+i);
	scanf("%d",&K);
	solve();
	return 0;
}