#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 9; int n, K, a[N], b[N]; 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; } 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]); } S = n + 1, T = cntn = S + 2; for (int i = 1; i <= n; i++) { add(S, i, 1, a[i]); add(i, T - 1, 1, b[i]); } for (int i = 1; i < n; i++) add(i, i + 1, K, 0); add(T - 1, T, K, 0); MSMF(), printf("%lld\n", cost); return 0; }