#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <iomanip> 
#include <vector> 
#include <set> 
#include <algorithm> 
#define MAXN 0x7fffffff 
using namespace std; 
int a[25][2],b,c,d,l,k,x,y;
set<int> s,t[2];
bool bo;
set <int>::iterator m,n,z; 
int main(void) 
{ 
    freopen("monkeys.in","r",stdin); 
    freopen("monkeys.out","w",stdout); 
    scanf("%d%d",&b,&c);
    for (d=0;d<c;d++) scanf("%d%d",&a[d][0],&a[d][1]);
    scanf("%d",&k);
    for (l=0;l<c;l++)
    {
        s.insert(a[l][1]);
        t[bo].insert(a[l][1]);
    }
    for (x=1;x<b;x++)
    {
        for (m=t[bo].begin();m!=t[bo].end();m++)
        {
            y=*m;
            for (l=0;l<c;l++)
                if (y%(a[l][0]-1)==0)
                {
                    s.insert(y/(a[l][0]-1)*a[l][0]+a[l][1]);
                    t[!bo].insert(y/(a[l][0]-1)*a[l][0]+a[l][1]);
                }
        }
        t[bo].clear();
        bo=!bo;
    }
    if (k>s.size()) printf("-1");
        else
        {
            if (k<s.size()/2)
            {
                y=0;
                for (m=s.begin();m!=s.end();m++)
                {
                    y++;
                    if (y==k) break;
                }
                y=*m;
                printf("%d",y);
            }
                else
                {
                    y=s.size();
                    for (m=s.end();m!=s.begin();m--)
                    {
                        if (y==k) break;
                        y--;
                    }
                    m--;
                    y=*m;
                    printf("%d",y);
                }
        }
    fclose(stdin); 
    fclose(stdout); 
    return 0; 
}