#3838. [Pa2013]Raper

内存限制:128 MiB 时间限制:60 Sec

题目描述

你需要生产k张光盘。每张光盘需要经过两道工序:先在A工厂进行挤压,然后送到B工厂涂上反光层。
共有n天时间,你知道每天A,B两家工厂的收费。一家工厂一天只能对一张光盘进行操作。同一天内一张光盘先后在A,B工厂被操作是允许的。你可以假定将只经过A操作的半成品暂存起来不需花费额外代价。
求出生产k张光盘的最小总花费。

输入格式

第一行两个整数n,k(1<=k<=n<=500000)。
第二行n个整数,表示A工厂每天的收费。
第三行n个整数,表示B工厂每天的收费。(收费均不超过10^9)

输出格式

输出最小总花费。

样例

样例输入


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

样例输出


			
32
样例解释:
第一张盘:第1天A,第1天B。
第二张盘:第2天A,第4天B。
第三张盘:第3天A,第5天B。
第四张盘:第6天A,第8天B。

数据范围与提示