题目描述

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。

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

求生产出 $k$ 张光盘的最小花费。

输入格式

第一行包含两个整数 $n, k$，表示有 $n$ 天，要生产 $k$ 张光盘。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 A 工厂加工光盘的花费。

第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 B 工厂加工光盘的花费。

输出格式

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

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

32

提示

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

注：添加了 2 组 Hack 数据，如未通过将扣除 3 分。