J

#include <bits/stdc++.h>

using namespace std;

#define fixed(n) fixed << setprecision(n)
#define ceil(n, m) (((n) + (m) - 1) / (m))
#define add_mod(a, b, m) (((a % m) + (b % m)) % m)
#define sub_mod(a, b, m) (((a % m) - (b % m) + m) % m)
#define mul_mod(a, b, m) (((a % m) * (b % m)) % m)
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define sz(x) int(x.size())
#define debug(x) cout << #x << ": " << (x) << "\n";
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define EPS 1e-9
constexpr int INF = 1 << 30, Mod = 1e9 + 7;
constexpr ll LINF = 1LL << 62;
#define PI acos(-1)
template < typename T = int > using Pair = pair < T, T >;
vector < string > RET = {"NO", "YES"};

template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
    for (auto &x : v) in >> x;
    return in;
}

template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
    for (const T &x : v) out << x << ' ';
    return out;
}

template < typename T = int > struct Stack {

    vector < T > st, Monotonic;
    T DEFAULT = INF;

    Stack() {
        Monotonic = {DEFAULT}, st = {};
    }

    T operation(T a, T b){
        return min(a, b);
    }

    void push(T x){
        st.emplace_back(x);
        Monotonic.push_back(operation(Monotonic.back(), x));
    }

    T pop(){
        T res = st.back();
        st.pop_back();
        Monotonic.pop_back();
        return res;
    }

    bool empty(){
        return st.empty();
    }

    T Monotonic_val(){
        return Monotonic.back();
    }

    int size(){
        return st.size();
    }

};

template < typename T = int > struct Monotonic_Queue {

    Stack < T > s1, s2;

    Monotonic_Queue () {
        s1 = Stack < T > (), s2 = Stack < T > ();
    }

    T operation(T a, T b){
        return min(a, b);
    }

    void push(T x){
        s2.push(x);
    }

    void pop(){
        if(s1.empty()){
            while(!s2.empty())
                s1.push(s2.pop());
        }
        s1.pop();
    }

    bool is_good(){
        return operation(s1.Monotonic_val(), s2.Monotonic_val()) == 1;
    }

    T Monotonic_val(){
        return operation(s1.Monotonic_val(), s2.Monotonic_val());
    }

    int size(){
        return s1.size() + s2.size();
    }
};


int n, k, mm;
vector < int > keys, c, primes;

constexpr int MaxN = 31625;
bool is_prime[MaxN];

void sieve(){
    memset(is_prime, true, sizeof is_prime);
    is_prime[0] = is_prime[1] = false;
    for(ll i = 2; i < MaxN; i++)
        if(is_prime[i]){
            primes.push_back(i);
            for(ll j = i * i; j < MaxN; j += i)
                is_prime[j] = false;
        }
}

int prime_factor(int x){
    for(auto& p : primes)
        if(x % p == 0)
            return p;
    return x;
}

bool is_good(int m){
    vector < ll > dp(n + 5, INF);
    dp[0] = 0;
    Monotonic_Queue < ll > q;
    q.push(0);
    for(int i = 1; i <= k && i <= n + 1; i++){
        if(keys[i] <= m)
            dp[i] = c[i];
        q.push(dp[i]);
    }
    q.pop();
    for(int i = k + 1; i <= n + 1; i++){
        if(keys[i] <= m)
            dp[i] = q.Monotonic_val() + c[i];
        q.push(dp[i]);
        q.pop();
    }
    return dp[n + 1] <= mm;
}

void Solve(){
    sieve();
    cin >> n >> k >> mm;
    if(k > n)
        return cout << 0 << '\n', void();
    keys = c = vector < int > (n + 5);
    for(int i = 1; i <= n; i++) cin >> keys[i], keys[i] = prime_factor(keys[i]);
    for(int i = 1; i <= n; i++) cin >> c[i];
    int l = 2, r = 1e9, ans = -1;
    while(l <= r){
        int m = l + (r - l) / 2;
        (is_good(m) ? ans = m, r = m - 1 : l = m + 1);
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int test_cases = 1;
    // cin >> test_cases;
    for(int tc = 1; tc <= test_cases; tc++){
        // cout << "Case #" << tc << ": ";
        Solve();
    }
    return 0;
}