#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; auto ans = min({a[la] * (rb - lb) + b[rb] * (ra - la), b[lb] * (ra - la) + a[ra] * (rb - lb), solve(la, ma, lb, mb) + solve(ma, ra, mb, rb)}); ans = min(ans, a[la] * (mb - lb) + solve(la, ra, mb, rb)); ans = min(ans, b[lb] * (ma - la) + solve(ma, ra, lb, rb)); ans = min(ans, a[ra] * (rb - mb) + solve(la, ra, lb, mb)); ans = min(ans, b[rb] * (ra - ma) + solve(la, ma, lb, 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(); }