#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// Using a large constant for infinity in the context of flow capacities.
const long long INF = 1e18;
// Defines a directed edge in the flow network.
struct Edge {
int to;
long long capacity;
int rev; // Index of the reverse edge in the adjacency list of 'to'.
};
// Global variables for the graph and flow algorithm.
vector<vector<Edge>> adj;
vector<int> level;
vector<int> iter; // Using int instead of size_t to save memory.
vector<pair<int, int>> seg_tree_children; // Stores children for segment tree nodes.
vector<int> v_nodes; // Stores the graph node indices for one type of diagonal.
// Adds a directed edge and its corresponding residual edge to the graph.
void add_edge(int u, int v, long long cap) {
adj[u].push_back({v, cap, (int)adj[v].size()});
adj[v].push_back({u, 0, (int)adj[u].size() - 1});
}
// Performs a Breadth-First Search (BFS) to build the level graph for Dinic's algorithm.
bool bfs(int s, int t) {
level.assign(adj.size(), -1);
vector<int> q;
q.reserve(adj.size()); // Pre-allocates memory to avoid reallocations.
level[s] = 0;
q.push_back(s);
size_t head = 0;
while (head < q.size()) {
int u = q[head++];
for (const auto& edge : adj[u]) {
if (edge.capacity > 0 && level[edge.to] < 0) {
level[edge.to] = level[u] + 1;
q.push_back(edge.to);
}
}
}
return level[t] != -1;
}
// Performs a Depth-First Search (DFS) to find augmenting paths in the level graph.
long long dfs(int u, int t, long long f) {
if (u == t) return f;
for (int& i = iter[u]; i < (int)adj[u].size(); ++i) {
Edge& e = adj[u][i];
if (e.capacity > 0 && level[u] < level[e.to]) {
long long d = dfs(e.to, t, min(f, e.capacity));
if (d > 0) {
e.capacity -= d;
adj[e.to][e.rev].capacity += d;
return d;
}
}
}
return 0;
}
// Dinic's max-flow algorithm to compute the maximum flow from source 's' to sink 't'.
long long max_flow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
iter.assign(adj.size(), 0);
long long f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
// Recursively builds a segment tree to represent connections efficiently.
int build_seg_tree(int l, int r, int& node_idx, int seg_base_idx) {
int curr_node = node_idx++;
if (l == r) {
add_edge(curr_node, v_nodes[l], INF);
} else {
int mid = l + (r - l) / 2;
int child1 = build_seg_tree(l, mid, node_idx, seg_base_idx);
int child2 = build_seg_tree(mid + 1, r, node_idx, seg_base_idx);
seg_tree_children[curr_node - seg_base_idx] = {child1, child2};
add_edge(curr_node, child1, INF);
add_edge(curr_node, child2, INF);
}
return curr_node;
}
// Queries the segment tree to add edges from a single u_node to a range of v_nodes.
void query_seg_tree(int node_idx, int seg_base_idx, int l, int r, int ql, int qr, int u_node) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
add_edge(u_node, node_idx, INF);
return;
}
int mid = l + (r - l) / 2;
pair<int, int> children = seg_tree_children[node_idx - seg_base_idx];
if (children.first != -1) {
query_seg_tree(children.first, seg_base_idx, l, mid, ql, qr, u_node);
}
if (children.second != -1) {
query_seg_tree(children.second, seg_base_idx, mid + 1, r, ql, qr, u_node);
}
}
// Solves the problem for diagonals of a single parity.
long long solve_for_parity(int m, int n, const vector<long long>& c1, const vector<long long>& c2, int parity) {
vector<long long> costs1, costs2;
vector<int> i_orig, j_orig;
for (int i = 1 - n; i <= m - 1; ++i) {
if (abs(i % 2) == parity) {
i_orig.push_back(i);
costs1.push_back(c1[i + n - 1]);
}
}
for (int j = 0; j <= m + n - 2; ++j) {
if (j % 2 == parity) {
j_orig.push_back(j);
costs2.push_back(c2[j]);
}
}
if (costs1.empty() || costs2.empty()) return 0;
int num_u = costs1.size();
int num_v = costs2.size();
// Tighter estimation for memory allocation.
// A segment tree on num_v leaves has at most 2*num_v nodes.
int num_seg_nodes_est = (num_v > 0) ? 2 * num_v : 0;
int total_nodes_est = 2 + num_u + num_v + num_seg_nodes_est;
adj.assign(total_nodes_est, vector<Edge>());
int S = 0, T = 1;
vector<int> u_nodes(num_u);
v_nodes.assign(num_v, 0);
int node_idx = 2;
for (int i = 0; i < num_u; ++i) u_nodes[i] = node_idx++;
for (int i = 0; i < num_v; ++i) v_nodes[i] = node_idx++;
for (int i = 0; i < num_u; ++i) add_edge(S, u_nodes[i], costs1[i]);
for (int i = 0; i < num_v; ++i) add_edge(v_nodes[i], T, costs2[i]);
int seg_base_idx = node_idx;
int seg_root = -1;
if (num_v > 0) {
seg_tree_children.assign(num_seg_nodes_est, {-1, -1});
seg_root = build_seg_tree(0, num_v - 1, node_idx, seg_base_idx);
}
for (int u_idx = 0; u_idx < num_u; ++u_idx) {
int i_val = i_orig[u_idx];
// Corrected calculation for the range of intersecting diagonals.
long long j_start_val = abs((long long)i_val);
long long j_end_val = min((long long)2 * m - 2 - i_val, (long long)2 * n - 2 + i_val);
if (j_start_val > j_end_val) continue;
auto it_start = lower_bound(j_orig.begin(), j_orig.end(), j_start_val);
if (it_start == j_orig.end() || *it_start > j_end_val) continue;
auto it_end = upper_bound(j_orig.begin(), j_orig.end(), j_end_val);
--it_end;
int v_idx_start = distance(j_orig.begin(), it_start);
int v_idx_end = distance(j_orig.begin(), it_end);
if (v_idx_start <= v_idx_end && seg_root != -1) {
query_seg_tree(seg_root, seg_base_idx, 0, num_v - 1, v_idx_start, v_idx_end, u_nodes[u_idx]);
}
}
adj.resize(node_idx); // Trim unused pre-allocated memory.
return max_flow(S, T);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m, n;
cin >> m >> n;
vector<long long> c1(m + n - 1), c2(m + n - 1);
for (int i = 0; i < m + n - 1; ++i) cin >> c1[i];
for (int i = 0; i < m + n - 1; ++i) cin >> c2[i];
long long total_cost = 0;
total_cost += solve_for_parity(m, n, c1, c2, 0); // Even parity
total_cost += solve_for_parity(m, n, c1, c2, 1); // Odd parity
cout << total_cost << endl;
return 0;
}
