著名的 bajtocki 说唱歌手 Bitbot 计划发行他最新专辑《来自音响的字节》的特别版本。该专辑将以黑胶唱片（俗称“vinyl”）为载体，在压制完成后再覆盖上闪粉。

Bitbot 已经与唱片压制厂以及闪粉加工厂（即负责给物体覆盖闪粉的公司）签署了协议，共同制作该专辑的 $k$ 张唱片。压制厂和闪粉厂每天都只能处理一张唱片。当然，每张唱片必须先压制，然后才能覆盖闪粉。幸运的是，同一张唱片可以在同一天在两家工厂都完成处理。

我们的说唱歌手现在正在研究未来 $n$ 天内使用压制厂和闪粉厂服务的价格列表。请帮他选择在哪些天安排在两个工厂中制作 $k$ 张唱片，以最小化总成本。你可以假设 Bitbot 能够无限期地储存已压制但未覆盖闪粉的唱片，而不会产生额外费用。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 500\,000$）。第二行包含 $n$ 个正整数，每个不超过 $10^{9}$ —— 表示接下来几天每一天压制唱片的成本。第三行包含 $n$ 个正整数，每个不超过 $10^{9}$ —— 表示接下来几天每一天覆盖闪粉的成本。

输出格式

你的程序应输出一个整数 —— 制作 $k$ 张覆盖了闪粉的唱片的最小总成本。

样例

输入

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

输出

32

说明

一个示例性的最优解是：在第一天压制并覆盖第一张唱片，在第二天压制第二张唱片并在第四天覆盖，在第三天压制第三张唱片并在第五天覆盖，在第六天压制第四张唱片并在第八天覆盖。