N. April Fools' Problem (medium)

#pragma GCC optimize("Ofast,unroll-loops")
#include <algorithm>
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define lsb(x) (x & (-x))

using namespace std;

#define int long long

inline bool ckmin(int &a, int b) { if (a <= b) return false; else a = b; return true; }
inline bool ckmax(int &a, int b) { if (a >= b) return false; else a = b; return true; }

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 2205;
const int PMAX = 10;
const int INF = 2e18+5;

struct Edge {
    int dest, cap, cost, other;
};

int n, k;
int a[NMAX], b[NMAX];
int source, sink;
vector<Edge> g[NMAX];
int dist[NMAX], pi[NMAX], pi2[NMAX];
int vis[NMAX];
bool inq[NMAX];
pii nxt[NMAX];

void add_edge(int x, int y, int cap, int cost) {
    if (!cap) return;
    g[x].push_back({ y, cap, cost, sz(g[y]) });
    g[y].push_back({ x, 0, -cost, sz(g[x]) - 1 });
}

void read() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
}

void init_pi() {
    for (int i = 1; i <= n; i++)
        pi[i] = INF;
    pi[source] = 0;

    int mn = INF;
    for (int i = 1; i <= n - 2; i++)
        mn = min(mn, a[i]);
    for (int i = 1; i <= n - 2; i++)
        pi[i] = mn;

    mn = INF;
    for (int i = n - 2; i >= 1; i--) {
        mn = min(mn, b[i]);
        pi[sink] = min(pi[sink], a[i] + mn);
    }
}

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        vis[i] = false;
        pi2[i] = pi[i];
    }

    priority_queue<pair<ll, int32_t>> pq;

    pq.push({0, source});
    dist[source] = pi[source] = 0;
    nxt[source] = {0, 0};
    int32_t i = 0;

    while (!pq.empty()) {
        int u = pq.top().se;

        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        i = 0;
        for (auto &it : g[u]) {
            if (it.cap && ckmin(dist[it.dest], dist[u] + it.cost + pi2[u] - pi2[it.dest])) {
                pi[it.dest] = pi[u] + it.cost;
                nxt[it.dest] = { u, i };
                pq.push({-dist[it.dest], it.dest});
            }
            i++;
        }
    }
}

int mcf(int max_flow) {
    int min_cost = 0;
    init_pi();
    while (dijkstra(), dist[sink] != INF && max_flow) {
        int flow = max_flow, cost = 0;
        for (int u = sink; u != source; u = nxt[u].fi) {
            Edge &e = g[nxt[u].fi][nxt[u].se];
            cost += e.cost;
            ckmin(flow, e.cap);
        }
        for (int u = sink; u != source; u = nxt[u].fi) {
            Edge &e = g[nxt[u].fi][nxt[u].se];
            e.cap -= flow;
            g[u][e.other].cap += flow;
        }
        max_flow -= flow;
        min_cost += flow * cost;
    }
    return min_cost;
}

int solve() {
    source = n + 1, sink = n + 2;
    for (int i = 1; i <= n; i++) {
        add_edge(source, i, 1, a[i]);
        add_edge(i, sink, 1, b[i]);
        if (i != n)
            add_edge(i, i + 1, k, 0);
    }
    n += 2;
    return mcf(k);
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    read();
    cout << solve() << endl;
    return 0;
}