UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3838. [Pa2013]Raper

Statistics 下载数据

Description

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

Input

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

Output

输出最小总花费。

Sample Input

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

Sample Output

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

Hint

Source