human
I found an interesting problem on https://codeforces.com/problemset/problem/802/N:
The marmots need to prepare k problems for HC^2 over n days. Each problem, once prepared, also has to be printed.

The preparation of a problem on day i (at most one per day) costs a_{i} CHF, and the printing of a problem on day i (also at most one per day) costs b_{i} CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine).

What is the minimum cost of preparation and printing?

-----Input-----

The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a_1, ..., a_{n} ($1 \leq a_{i} \leq 10^{9}$) — the preparation costs. The third line contains n space-separated integers b_1, ..., b_{n} ($1 \leq b_{i} \leq 10^{9}$) — the printing costs.

-----Output-----

Output the minimum cost of preparation and printing k problems — that is, the minimum possible sum a_{i}_1 + a_{i}_2 + ... + a_{i}_{k} + b_{j}_1 + b_{j}_2 + ... + b_{j}_{k}, where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n, 1 ≤ j_1 < j_2 < ... < j_{k} ≤ n and i_1 ≤ j_1, i_2 ≤ j_2, ..., i_{k} ≤ j_{k}.

-----Example-----
Input
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

Output
32

-----Note-----

In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is Python program to print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

from itertools import count
from collections import deque
from heapq import heappop, heappush
 
class Edge(object):
    __slots__ = ('x', 'y', 'cap', 'cost', 'inv')
    def __repr__(self):
        return f'{self.x}-->{self.y} ({self.cap} , {self.cost})'

class MCFP(list):
    inf = float('inf')
    
    def add(G, x, y, cap, cost):
        G.extend(([] for i in range(max(0,max(x,y)+1-len(G)))))
        e = Edge()
        e.x=x ; e.y=y; e.cap=cap; e.cost=cost
        z = Edge()
        z.x=y ; z.y=x; z.cap=0; z.cost=-cost
        e.inv=z ; z.inv=e
        G[x].append(e)
        G[y].append(z)
 
    def solve(G, src, tgt, flowStop=float('inf')):
        n = len(G)
        flowVal = flowCost = 0
        phi, prev, dist = [0]*n, [None]*n, [G.inf]*n
        for it in count():
            G.shortest(src, phi, prev, dist, tgt)
            if prev[tgt]==None:
                break
            p = list(G.backward(tgt, src, prev))
            z = min(e.cap for e in p)
            for e in p: e.cap -= z ; e.inv.cap += z
            flowVal += z
            flowCost += z * (dist[tgt] - phi[src] + phi[tgt])
            if flowVal==flowStop: break
            for i in range(n):
                if prev[i] != None:
                    phi[i] += dist[i]
                    dist[i] = G.inf
        #print(it)
        return flowVal, flowCost

    def backward(G, x, src, prev):
        while x!=src: e = prev[x] ; yield e ; x = e.x

    def shortest_(G, src, phi, prev, dist, tgt):
        prev[tgt] = None
        dist[src] = 0
        Q = [(dist[src], src)]
        k = 0
        while Q:
            k += 1
            d, x = heappop(Q)
            if dist[x]!=d: continue
            for e in G[x]:
                if e.cap <= 0: continue
                dy = dist[x] + phi[x] + e.cost - phi[e.y]
                if dy < dist[e.y]:
                    dist[e.y] = dy
                    prev[e.y] = e
                    heappush(Q, (dy, e.y))
        print(k)
        return

    def shortest(G, src, phi, prev, dist, tgt):
       ...