#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10, C = 30;
int n, c, k, t, h, s, p;
int x[C], y[C], d[N], a[N], w[N];
void Getup(int u) {
    while(u > 1) {
        int v = u / 2;
        fprintf(stderr, "(%d). %d %d %d %d\n", p, u, v, d[u], d[v]);
        if(a[d[u]] < a[d[v]] || (a[d[u]] == a[d[v]] && d[u] < d[v])) {
            swap(d[u], d[v]);
            swap(w[d[u]], w[d[v]]);
            u = v;
        } else break;
    }
}
void Getdown(int u) {
    int v = u * 2;
    fprintf(stderr, "[%d]. %d %d %d %d\n", p, u, v, d[u], d[v]);
    if(a[d[v]] < a[d[u]] || (a[d[u]] == a[d[v]] && d[v] < d[u])) {
        swap(d[u], d[v]);
        swap(w[d[u]], w[d[v]]);
        Getup(v);
    }
}
void BFS() {
    int m, e;
    for(int i=1; i<=c; i++) if(!w[m = y[i]]) {
        t++; d[t] = m; a[m] = 1; w[m] = t;
        s++; Getup(t);
    }
    while(t && s < c*c + k) {
        m = d[1]; d[1] = d[t]; w[m] = 0; w[d[1]] = 1;
        t--; if(t > 0) Getdown(1);
        if(a[m] < n) for(int i=1; i<=c; i++) if(m % (x[i]-1) == 0) {
            e = m / (x[i]-1) * x[i] + y[i];
            if(!a[e] || a[e] > a[m] + 1) {
                if(!a[e]) s++; a[e] = a[m] + 1;
                if(!w[e]) {
                    t++; w[e] = t; d[t] = e;
                }
                Getup(w[e]);
            }
        }
    }
}
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", x+i, y+i);
    scanf("%d", &k);
    BFS();
    if(s >= k) {
        int i = 0;
        while(k > 1) {
            while(!a[i]) i++;
            i++; k--;
        }
        while(!a[i]) i++;
        printf("%d\n", i);
    } else
        printf("%d\n", -1);
    return 0;
}