#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug false const int MAXH = 100 * 1000 + 17; int a[MAXH][2]; pii st[MAXH * 4][2]; vector<pii> vec; int h, W; void buduj (int p, int k, int i, int nr) { if (p == k) { st[i][nr] = {a[p][nr], p}; return; } int sr = (p + k)/ 2; buduj(p, sr, i * 2, nr); buduj(sr + 1, k, i * 2 + 1, nr); st[i][nr] = min(st[i * 2][nr], st[i * 2 + 1][nr]); } pii odczytaj (int p, int k, int a, int b, int i, int nr) { if (k < a || p > b) { return {INT_MAX, 0}; } if (a <= p && k <= b) { return st[i][nr]; } int sr = (p + k)/ 2; return min(odczytaj(p, sr, a, b, i * 2, nr), odczytaj(sr + 1, k, a, b, i * 2 + 1, nr)); } void dziel (pii p, pii k) { if (p.nd == k.nd) { for (int i = p.st; i <= k.st; i ++) { vec.pb({i, p.nd}); } return; } if (p.st == k.st) { for (int i = p.nd; i <= k.nd; i ++) { vec.pb({p.st, i}); } return; } pii sr = {-1, -1}; int rek = INT_MAX; if (p.st + 1 <= k.st - 1 && p.nd + 1 <= k.nd - 1) { pii w1 = odczytaj(0, h - 1, p.st + 1, k.st - 1, 1, 0); pii w2 = odczytaj(0, W - 1, p.nd + 1, k.nd - 1, 1, 1); rek = w1.st + w2.st; sr = {w1.nd, w2.nd}; } pii w = odczytaj(0, h - 1, p.st + 1, k.st, 1, 0); int akt = a[p.nd][1] + w.st; if (akt < rek) { rek = akt; sr = {w.nd, p.nd}; } w = odczytaj(0, h - 1, p.st, k.st - 1, 1, 0); akt = a[k.nd][1] + w.st; if (akt < rek) { rek = akt; sr = {w.nd, k.nd}; } w = odczytaj(0, W - 1, p.nd + 1, k.nd, 1, 1); akt = a[p.st][0] + w.st; if (akt < rek) { rek = akt; sr = {p.st, w.nd}; } w = odczytaj(0, W - 1, p.nd, k.nd - 1, 1, 1); akt = a[k.st][0] + w.st; if (akt < rek) { rek = akt; sr = {k.st, w.nd}; } dziel(p, sr); dziel(sr, k); } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> h >> W; for (int i = 0; i < h; i ++) { cin >> a[i][0]; } for (int i = 0; i < W; i ++) { cin >> a[i][1]; } buduj(0, h - 1, 1, 0); buduj(0, W - 1, 1, 1); dziel({0, 0}, {h - 1, W - 1}); sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); ll wyn = 0; for (int i = 0; i < h + W - 2; i ++) { if (vec[i].st == vec[i + 1].st) { wyn += ll(a[vec[i].st][0]); } else { wyn += ll(a[vec[i].nd][1]); } } cout << wyn << "\n"; return 0; }