题目描述

$n$ 道题，第 $i$ 天可以花费 $a_i$ 准备一道题，花费 $b_i$ 打印一道题，每天最多准备一道，最多打印一道，准备的题可以留到以后打印，求最少花费使得准备并打印 $k$ 道题。

输入格式

第一行两个整数 $n,k$。

接下来两行，分别是 $a_i$，$b_i$。

输出格式

输出一个整数表示答案。

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

32

提示

对于 $50\%$ 的数据，$1\le k\le n\le 2200$。

对于 $100\%$ 的数据，$1\le k\le n\le 500000$。$1\le a_i, b_i\le 10^9$。