[PA2013] Raper

题目描述

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序:先在 A 工厂进行挤压,再送到 B 工厂涂上反光层。 你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间,每天可以先送一张光盘到 A 工厂(或者不送),然后再送一张已经在 A 工厂加工过的光盘到 B 工厂(或者不送),每家工厂一天只能对一张光盘进行操作,同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。 求生产出 $k$ 张光盘的最小花费。

输入输出格式

输入格式


第一行包含两个整数 $n, k$,表示有 $n$ 天,要生产 $k$ 张光盘。 第二行包含 $n$ 个整数,第 $i$ 个整数表示第 $i$ 天送到 A 工厂加工光盘的花费。 第三行包含 $n$ 个整数,第 $i$ 个整数表示第 $i$ 天送到 B 工厂加工光盘的花费。

输出格式


输出一行一个整数,表示最小花费。

输入输出样例

输入样例 #1

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

输出样例 #1

32

说明

保证 $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$。 注:添加了 2 组 Hack 数据,如未通过将扣除 3 分。