budget c++

#include <bits/stdc++.h>

using namespace std;

int n, m, t;
long long p, s[103], r[103];
vector<int> g[10004], visited, assigned;

bool visit(int u) {
    if (visited[u] != t) visited[u] = t; else return false;

    for (int v:g[u])
        if (!assigned[v] || visit(assigned[v])) {
            assigned[v] = u;
            return true;
        }

    return false;
}

bool check(long long d) {
    for (int i = 1; i <= m; i++) g[i].resize(0);

    int nn = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (r[1] + s[i] * j - 1 <= d) {
                nn++;

                for (int k = 1; k <= m; k++)
                    if (r[k] + s[i] * j - 1 <= d) g[k].push_back(nn);
                    else break;
            } else break;

    visited.assign(m + 2, 0);
    assigned.assign(nn + 2, 0);

    t = 0;
    int res = 0;
    for (int i = 1; i <= m; i++) {
        t++;
        res += visit(i);
    }

    return (res >= m);
}

long long bina() {
    long long l = 0, r = 1000000000000015, res;
    while (l <= r) {
        long long m = (l + r) >> 1;

        if (check(m)) {
            res = m;
            r = m - 1;
        } else l = m + 1;
    }
    return res;
}

int main() {
    freopen("BUDGET.INP", "r", stdin);
    freopen("BUDGET.OUT", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = (p / s[i]) + int(p % s[i] > 0);
    }
    for (int i = 1; i <= m; i++) cin >> r[i];

    sort(r + 1, r + m + 1);

    cout << bina();
}