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: VERY_HARD
Tags: Sorting

Graph algorithms

Flows and cuts
Skill types: Sorting

Starter code:

Solutions:
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)
	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)
main()


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
		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)
main()