#include <bits/stdc++.h> #define rep(a,b,c) for(auto a = (b); a != (c); a++) #define repD(a,b,c) for(auto a = (b); a != (c); a--) #define repIn(a, b) for(auto& a : (b)) #define repIn2(a, b, c) for(auto& [a, b] : (c)) constexpr bool dbg = 1; #define DEBUG if constexpr(dbg) #define DC DEBUG std::cerr #define eol std::endl #define int long long #define ld long double #define pb push_back using namespace std; constexpr int inf = 2e18; int n, m; vector<int> a, b; map<array<int, 4>, int> mp; int solve(int la, int ra, int lb, int rb); int _solve(int la, int ra, int lb, int rb) { if(la == ra) return a[la] * (rb - lb); if(lb == rb) return b[lb] * (ra - la); if(la + 1 == ra) { int ans = inf; rep(i, lb, rb + 1) ans = min(ans, a[la] * (i - lb) + b[i] + a[ra] * (rb - i)); return ans; } if(lb + 1 == rb) { int ans = inf; rep(i, la, ra + 1) ans = min(ans, b[lb] * (i - la) + a[i] + b[rb] * (ra - i)); return ans; } pair<int, int> mn = {inf, -1}; rep(i, la + 1, ra) mn = min(mn, {a[i], i}); int ma = mn.second; mn = {inf, -1}; rep(i, lb + 1, rb) mn = min(mn, {b[i], i}); int mb = mn.second; int mna = min({a[la], a[ma], a[ra]}); int mnb = min({b[lb], b[mb], b[rb]}); auto ans = min(a[la] * (rb - lb) + b[rb] * (ra - la), b[lb] * (ra - la) + a[ra] * (rb - lb)); ans = min(ans, min((ma - la) * b[lb] + (mb - lb) * a[ma], (mb - lb) * a[la] + (ma - la) * b[mb]) + min((ra - ma) * b[mb] + (rb - mb) * a[ra], (rb - mb) * a[ma] + (ra - ma) * b[rb])); if(max(a[la], a[ra]) <= a[ma] || max(b[lb], b[rb]) <= b[mb]) return ans; if((a[la] == mna && b[rb] == mnb) || (a[ra] == mna && b[lb] == mnb)) return mna * (rb - lb) + mnb * (ra - la); if(a[la] == mna && b[lb] != mnb) return mna * (mb - lb) + solve(la, ra, mb, rb); if(a[ra] == mna && b[rb] != mnb) return mna * (rb - mb) + solve(la, ra, lb, mb); if(b[lb] == mnb && a[la] != mna) return mnb * (ma - la) + solve(ma, ra, lb, rb); if(b[rb] == mnb && a[ra] != mna) return mnb * (ra - ma) + solve(la, ma, lb, rb); if(a[la] == mna && b[lb] == mnb) return min(mna * (mb - lb) + solve(la, ra, mb, rb), mnb * (ma - la) + solve(ma, ra, lb, rb)); if(a[ra] == mna && b[rb] == mnb) return min(mna * (rb - mb) + solve(la, ra, lb, mb), mnb * (ra - ma) + solve(la, ma, lb, rb)); ans = min(ans, solve(la, ma, lb, mb) + solve(ma, ra, mb, rb)); return ans; } int solve(int la, int ra, int lb, int rb) { array<int, 4> ar = {la, ra, lb, rb}; if(!mp.count(ar)) mp[ar] = _solve(la, ra, lb, rb); return mp[ar]; } void bru() { vector<vector<array<int, 3>>> dp(n, vector<array<int, 3>>(m, {inf, -1, -1})); dp[0][0] = {0, 0, 0}; rep(i, 0, n) rep(j, 0, m) { auto x = dp[i][j][0]; if(i < n - 1) dp[i + 1][j] = min(dp[i + 1][j], {x + b[j], i, j}); if(j < m - 1) dp[i][j + 1] = min(dp[i][j + 1], {x + a[i], i, j}); } stack<array<int, 3>> s; int x = n - 1, y = m - 1; while(x || y) { auto [d, nx, ny] = dp[x][y]; s.push({d - dp[nx][ny][0], x, y}); x = nx, y = ny; } cout << dp[n - 1][m - 1][0] << '\n'; DC << "0, 0\n"; while(s.size()) { auto [c, x, y] = s.top(); s.pop(); DC << " -> " << x << ", " << y << " \tcosting " << c << '\n'; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; a.resize(n), b.resize(m); repIn(i, a) cin >> i; repIn(i, b) cin >> i; cout << solve(0, n - 1, 0, m - 1) << '\n'; //bru(); }