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.

Difficulty: interview

Starter code:

Solutions:
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):
        prev[tgt] = None
        dist[src] = 0
        Q = deque([src])
        inQ = [0]*len(G)
        sumQ = 0
        while Q:
            x = Q.popleft()
            inQ[x] = 0
            sumQ -= dist[x]
            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
                    if inQ[e.y]==0:
                        inQ[e.y]=1
                        sumQ += dy
                        if Q and dy > dist[Q[0]]: Q.append(e.y)
                        else: Q.appendleft(e.y)
                        avg = sumQ/len(Q)
                        while dist[Q[0]] > avg: Q.append(Q.popleft())
        return

    def shortest_(G, src, phi, prev, dist, tgt):
        prev[tgt] = None
        dist[src] = 0
        H = [(0, src)]
        inQ = [0]*len(G)
        k = 0
        while H:
            k += 1
            d, x = heappop(H)
            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(H, (dy, e.y))
        print(k)
        return

import sys, random
ints = (int(x) for x in sys.stdin.read().split())
sys.setrecursionlimit(3000)

def main():
    n, k = (next(ints) for i in range(2))
    a = [next(ints) for i in range(n)]
    b = [next(ints) for i in range(n)]
    G = MCFP()
    src, tgt, the_src = 2*n+1, 2*n+2, 2*n+3
    G.add(the_src, src, k, 0)
    for i in range(n):
        G.add(src, i, 1, 0)
        G.add(i, i+n, 1, a[i])
        G.add(i+n, tgt, 1, b[i])
        if i+1<n:
            G.add(i, i+1, n, 0)
            G.add(i+n, i+n+1, n, 0)
    flowVal, ans = G.solve(the_src, tgt, k)
    assert flowVal == k
    print(ans)
    return

def test(n,k):
    R = random.Random(0)
    yield n ; yield k
    for i in range(n): yield R.randint(1, 10**9)
    for i in range(n): yield R.randint(1, 10**9)

#ints=test(1000, 800)

main()

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

class MCFP(list):
    def add(G, x, y, cap, cost):
        n = max(x, y) + 1
        while len(G)<n: G.append([])
        e = Edge() ; G[x].append(e)
        w = Edge() ; G[y].append(w)
        e.x=x ; e.y=y; e.cap=cap; e.cost=cost ; w.inv=e        
        w.x=y ; w.y=x; w.cap=0; w.cost=-cost ; e.inv=w
 
    def solve(G, src, tgt, flowStop=float('inf'), inf=float('inf')):
        flowVal = flowCost = 0
        n = len(G)
        G.inQ = [0]*n
        G.phi = h = [0]*n
        G.prev = p = [None]*n
        G.dist = d = [inf]*n
        G.SPFA(src)
        while p[tgt]!=None and flowVal<flowStop:
            b = [] ; x = tgt
            while x!=src: b.append(p[x]) ; x=p[x].x
            z = min(e.cap for e in b)
            for e in b: e.cap-=z ; e.inv.cap+=z
            flowVal += z
            flowCost += z * (d[tgt] - h[src] + h[tgt])
            for i in range(n):
                if p[i]!=None: h[i]+=d[i] ; d[i]=inf
            p[tgt] = None
            G.SPFA(src)
        return flowVal, flowCost

    def SPFA(G, src):
        inQ = G.inQ ; prev = G.prev
        d = G.dist ; h = G.phi
        d[src] = 0
        Q = deque([src])
        while Q:
            x = Q.popleft()
            inQ[x] = 0
            for e in G[x]:
                if e.cap <= 0: continue
                y = e.y ; dy = d[x] + h[x] + e.cost - h[y]
                if dy < d[y]:
                    d[y] = dy ; prev[y] = e
                    if inQ[y]==0:
                        inQ[y] = 1
                        if not Q or dy > d[Q[0]]: Q.append(y)
                        else: Q.appendleft(y)
        return

import sys, random
ints = (int(x) for x in sys.stdin.read().split())
sys.setrecursionlimit(3000)

def main():
    n, k = (next(ints) for i in range(2))
    a = [next(ints) for i in range(n)]
    b = [next(ints) for i in range(n)]
    G = MCFP()
    src, tgt = 2*n+1, 2*n+2
    for i in range(n):
        G.add(src, i, 1, 0)
        G.add(i, i+n, 1, a[i])
        G.add(i+n, tgt, 1, b[i])
        if i+1<n:
            G.add(i, i+1, n, 0)
            G.add(i+n, i+n+1, n, 0)
    flowVal, ans = G.solve(src, tgt, k)
    assert flowVal == k
    print(ans)
    #print(G)
    return

def test(n,k):
    R = random.Random(0)
    yield n ; yield k
    for i in range(n): yield R.randint(1, 10**9)
    for i in range(n): yield R.randint(1, 10**9)

#ints=test(1000, 800)

main()