#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 9; int n, K, a[N], b[N]; namespace Sub1 { LL dp[109][309][309]; int Main() { for (int k = 1; k <= K; k++) { memset(dp[k], 0x3f, sizeof(dp[k])); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { dp[k][i][j] = dp[k - 1][i - 1][j - 1] + a[i] + b[j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[k][i][j] = min({dp[k][i][j], dp[k][i - 1][j], dp[k][i][j - 1]}); } } } printf("%lld\n", dp[K][n][n]); return 0; } } const int maxN = 7e5 + 9, maxM = 3e6 + 9; struct Edge { int v, w, c, nxt; } E[maxM]; int head[maxN], cur[maxN], tot = 1, S, T, cntn; void Add(int u, int v, int w, int c) { E[++tot].v = v, E[tot].w = w, E[tot].c = c; E[tot].nxt = head[u], head[u] = tot; } void add(int u, int v, int w, int c) { Add(u, v, w, c), Add(v, u, 0, -c); } LL dis[maxN]; bool in[maxN], vis[maxN]; queue<int> q; bool spfa() { memset(dis, 0x3f, sizeof(LL) * (cntn + 9)); dis[S] = 0, q.push(S); while (!q.empty()) { int u = q.front(); q.pop(), in[u] = 0; for (int i = head[u]; i; i = E[i].nxt) { int v = E[i].v, w = E[i].w, c = E[i].c; if (w && dis[v] > dis[u] + c) { dis[v] = dis[u] + c; if (!in[v]) in[v] = 1, q.push(v); } } } return dis[T] != dis[0]; } LL cost; int dfs(int u, int f) { if (u == T) return f; int res = 0; vis[u] = 1; for (int i = cur[u]; i && f; i = E[i].nxt) { cur[u] = i; int v = E[i].v, w = E[i].w, c = E[i].c; if (!vis[v] && w && dis[v] == dis[u] + c) { int x = dfs(v, min(w, f)); E[i].w -= x, E[i ^ 1].w += x; f -= x, res += x, cost += 1ll * x * c; } } vis[u] = 0; return res; } int MSMF() { int res = 0, x; while (spfa()) { for (int i = 1; i <= cntn; i++) cur[i] = head[i]; while (x = dfs(S, 2e9)) res += x; } return res; } struct seg { int lt[N << 2], rt[N << 2], id[N]; void build(int u, int l, int r) { lt[u] = l, rt[u] = r; if (l == r) { id[l] = u; return; } add(u, u << 1, 1e9, 0), add(u, u << 1 | 1, 1e9, 0); int mid = (l + r) >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); } void addedge(int u, int x, int y, int v) { if (x <= lt[u] && rt[u] <= y) { add(v, u, 1e9, 0); return; } int mid = (lt[u] + rt[u]) >> 1; if (x <= mid) addedge(u << 1, x, y, v); if (y > mid) addedge(u << 1 | 1, x, y, v); } } SegT; namespace Sub2 { int Main() { SegT.build(1, 1, n); for (int i = 1; i <= n; i++) { SegT.addedge(1, 1, i, n * 4 + i); } S = n * 4 + n + 1, T = cntn = S + 2; for (int i = 1; i <= n; i++) { add(S, n * 4 + i, 1, b[i]); add(SegT.id[i], T - 1, 1, a[i]); } add(T - 1, T, K, 0); MSMF(), printf("%lld\n", cost); return 0; } } int main() { scanf("%d%d", &n, &K); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &b[i]); } Sub2::Main(); return 0; }