#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; template auto range(T s, T e) { return views::iota(s, max(s, e)); } template auto range(T n) { return range(0, n); } template void take(vector& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; } template void sout(const Args &...args) { ((cout << args << ' '), ...); } template void soutn(const Args &...args) { ((cout << args << ' '), ...); cout << '\n'; } template struct In2 { T1 a; T2 b; friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; } }; template struct In3 { T1 a; T2 b; T3 c; friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; } }; template struct In4 { T1 a; T2 b; T3 c; T4 d; friend std::istream& operator>>(std::istream& is, In4& obj) { T1 t1; T2 t2; T3 t3; T4 t4; is >> t1 >> t2 >> t3 >> t4; obj = {t1, t2, t3, t4}; return is; } }; #ifdef LOCAL #include #else #define dump(...) ; #endif namespace { ll h, w, budget; vector> va, vcost; void read() { cin >> h >> w >> budget; va.resize(h); for (int i : range(h)) take(va[i], w); vcost.resize(h); for (int i : range(h)) take(vcost[i], w); } const ll inf = 1LL << 60; struct Mini { ll a, b; Mini(): a(inf), b(inf) {} void update(ll x) { if (x <= a) { b = a; a = x; } else if (x <= b) { b = x; } } }; ll solve(ll a, ll b, ll c, ll upper) { // maximize (a-bx)(c+x) /* ll naive = 0; for (ll x : range(upper + 1)) { naive = max(naive, (a - b * x) * (c + x)); } */ ll res = 0; ll x0 = (a / b - c) / 2; vector xc{0, upper, x0, x0 - 1, x0 + 1}; for (ll x : xc) if (0 <= x && x <= upper) { res = max(res, (a - b * x) * (c + x)); } // assert(naive == res); return res; } ll run() { vector vm1(h), vm2(w); vector sum1(h), sum2(w); for (int i : range(h)) for (int j : range(w)) { vm1[i].update(vcost[i][j]); vm2[j].update(vcost[i][j]); sum1[i] += va[i][j]; sum2[j] += va[i][j]; } ll res = 0; for (int i : range(h)) for (int j : range(w)) { ll c0 = vcost[i][j]; ll c1 = (c0 == vm1[i].a) ? vm1[i].b : vm1[i].a; ll c2 = (c0 == vm2[j].a) ? vm2[j].b : vm2[j].a; ll s1 = sum1[i]; ll s2 = sum2[j]; dump(i, j, " => ", c0, c1, c2, s1, s2); if (c1 > c2) { swap(c1, c2); swap(s1, s2); } // c1 <= c2 ll cand = 0; if (c0 <= c1) { dump("c0 is min"); ll inc = budget / c0; dump("inc", inc); cand = (s1 + inc) * (s2 + inc); } else { ll c2d = c2 / c1; ll b0 = budget / c1; if (c2 < c0) { dump("c0 is ignore"); // q + c'r = b' cand = solve(s1 + b0, c2d, s2, b0); } else { dump("c0 is between"); assert(c1 < c0 && c0 <= c2); // q + c'p = b' cand = solve(s1 + b0, c2d - 1, s2, b0); } } dump(i, j, " => ", cand); res = max(res, cand); } return res; } } // namespace template void exec(F f) { if constexpr (std::is_same_v) f(); else cout << f() << endl; } int main(int argc, char** argv) { cerr << fixed << setprecision(12); cout << fixed << setprecision(12); int testcase = 1; if (argc > 1) testcase = atoi(argv[1]); while (testcase--) { read(); } exec(run); }