4396. Ave Mujica

【题目背景】

【题目描述】

丰川祥子有 $k$ 张唱片需要生产，每张唱片需要先在 $A$ 工厂加工为半成品，再在 $B$ 工厂加工出来。

你知道每天 $A、B$ 工厂分别加工一张唱片的花费。你现在有 $n$ 天时间，每天可以先送一张唱片到 $A$ 工厂（或者不送），然后再送一张已经在 $A$ 工厂加工过的唱片到 $B$ 工厂（或者不送），每家工厂一天只能对一张唱片进行操作，同一张唱片在一天内生产出来是允许的。我们假定将未加工的或半成品的唱片保存起来不需要费用。

【输入格式】

第一行包含两个整数 $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

【数据规模与约定】

大样例

保证对于 $20 \%$ 的数据，满足 $n \le 10$。

保证对于 $30 \%$ 的数据，满足 $n \le 1000$。

保证 $1 \le k \le n \le 5 \times 10 ^ 5$, $1 \le a_i,b_i \le 10^9$。

【来源】

《Ave Mujica》