#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
using namespace std;
// Use a large enough value for infinity in the context of the problem's costs.
const long long INF = 4e14; // Sum of all possible costs is approx 2e5*2*1e9 = 4e14
struct Edge {
int to;
long long capacity;
int rev;
};
vector<vector<Edge>> adj;
vector<int> level;
vector<int> iter;
// Adds a directed edge from u to v with a certain capacity.
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}); // Residual edge
}
// Builds the level graph using BFS for Dinic's algorithm.
bool bfs(int s, int t) {
level.assign(adj.size(), -1);
vector<int> q;
q.push_back(s);
level[s] = 0;
int 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;
}
// Finds an augmenting path using DFS on the level graph.
long long dfs(int u, int t, long long f) {
if (u == t) return f;
for (int& i = iter[u]; i < 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;
}
// Computes the maximum flow from s to t using Dinic's algorithm.
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;
}
// Globals to be used by the segment tree functions
int m, n;
vector<int> lr_node_indices_global;
int seg_tree_nodes_start_global;
// Recursively builds the segment tree for min-cut graph optimization.
void build_seg_tree(int u, int l, int r) {
if (l == r) {
add_edge(seg_tree_nodes_start_global + u, lr_node_indices_global[l], INF);
return;
}
int mid = l + (r - l) / 2;
// Edges from parent to children in the segment tree
add_edge(seg_tree_nodes_start_global + u, seg_tree_nodes_start_global + 2 * u, INF);
add_edge(seg_tree_nodes_start_global + u, seg_tree_nodes_start_global + 2 * u + 1, INF);
build_seg_tree(2 * u, l, mid);
build_seg_tree(2 * u + 1, mid + 1, r);
}
// Adds edges from a source node to the segment tree nodes covering a target range.
void add_range_edges(int u, int l, int r, int target_l, int target_r, int from_node) {
if (r < target_l || l > target_r) return;
if (target_l <= l && r <= target_r) {
add_edge(from_node, seg_tree_nodes_start_global + u, INF);
return;
}
int mid = l + (r - l) / 2;
add_range_edges(2 * u, l, mid, target_l, target_r, from_node);
add_range_edges(2 * u + 1, mid + 1, r, target_l, target_r, from_node);
}
// Solves one of the two independent subproblems (even or odd parity).
long long solve_subproblem(const vector<pair<int, int>>& lr_diags, const vector<pair<int, int>>& rl_diags) {
if (lr_diags.empty() || rl_diags.empty()) {
return 0;
}
int p = lr_diags.size();
int q = rl_diags.size();
map<int, int> lr_id_to_idx;
for (int i = 0; i < p; ++i) {
lr_id_to_idx[lr_diags[i].first] = i;
}
// Define node indices for the graph
int s = 0;
int rl_nodes_start = 1;
int lr_nodes_raw_start = rl_nodes_start + q;
seg_tree_nodes_start_global = lr_nodes_raw_start + p;
int seg_tree_size = 4 * p;
int t = seg_tree_nodes_start_global + seg_tree_size;
int num_nodes = t + 1;
adj.assign(num_nodes, vector<Edge>());
// Set up global variables for segment tree construction
lr_node_indices_global.resize(p);
iota(lr_node_indices_global.begin(), lr_node_indices_global.end(), lr_nodes_raw_start);
// Add edges from source to RL-diagonal nodes
for (int i = 0; i < q; ++i) {
add_edge(s, rl_nodes_start + i, rl_diags[i].second);
}
// Add edges from LR-diagonal nodes to sink
for (int i = 0; i < p; ++i) {
add_edge(lr_nodes_raw_start + i, t, lr_diags[i].second);
}
// Build the segment tree over LR-diagonal nodes
if (p > 0) {
build_seg_tree(1, 0, p - 1);
}
// Connect RL-diagonal nodes to the segment tree
for (int i = 0; i < q; ++i) {
int d_rl = rl_diags[i].first;
long long drl_ll = d_rl;
long long n_ll = n;
long long m_ll = m;
// Calculate the range of LR-diagonal IDs that this RL-diagonal intersects
long long d_lr_min = max(-drl_ll, drl_ll - 2 * n_ll + 2);
long long d_lr_max = min(drl_ll, 2 * m_ll - 2 - drl_ll);
auto it_min = lr_id_to_idx.lower_bound(d_lr_min);
if (it_min == lr_id_to_idx.end() || it_min->first > d_lr_max) continue;
auto it_max = lr_id_to_idx.upper_bound(d_lr_max);
it_max--;
int idx_min = it_min->second;
int idx_max = it_max->second;
if (idx_min > idx_max) continue;
add_range_edges(1, 0, p - 1, idx_min, idx_max, rl_nodes_start + i);
}
return max_flow(s, t);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> m >> n;
vector<int> lr_costs(m + n - 1);
vector<int> rl_costs(m + n - 1);
for (int i = 0; i < m + n - 1; ++i) cin >> lr_costs[i];
for (int i = 0; i < m + n - 1; ++i) cin >> rl_costs[i];
vector<pair<int, int>> lr_even, lr_odd;
vector<pair<int, int>> rl_even, rl_odd;
// Partition diagonals by parity
for (int i = 0; i < m + n - 1; ++i) {
int id = i + 1 - n; // As per problem statement indexing
if (abs(id) % 2 == 0) {
lr_even.push_back({id, lr_costs[i]});
} else {
lr_odd.push_back({id, lr_costs[i]});
}
}
for (int i = 0; i < m + n - 1; ++i) {
int id = i; // As per problem statement indexing
if (id % 2 == 0) {
rl_even.push_back({id, rl_costs[i]});
} else {
rl_odd.push_back({id, rl_costs[i]});
}
}
long long total_cost = 0;
total_cost += solve_subproblem(lr_even, rl_even);
total_cost += solve_subproblem(lr_odd, rl_odd);
cout << total_cost << endl;
return 0;
}
