Description

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

共有n天时间，你知道每天A,B两家工厂的收费。一家工厂一天只能对一张光盘进行操作。同一天内一张光盘先后在A,B工厂被操作是允许的。你可以假定将只经过A操作的半成品暂存起来不需花费额外代价。

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

Format

Input

第一行两个整数n,k(1<=k<=n<=500000)。

第二行n个整数，表示A工厂每天的收费。

第三行n个整数，表示B工厂每天的收费。（收费均不超过10^9)

Output

输出最小总花费。

Samples

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。

Limitation