bzoj#P3838. [PA2013] Raper

[PA2013] Raper

题目描述

你需要生产 kk 张光盘。每张光盘都要经过两道工序:先在 A 工厂进行挤压,再送到 B 工厂涂上反光层。

你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 nn 天时间,每天可以先送一张光盘到 A 工厂(或者不送),然后再送一张已经在 A 工厂加工过的光盘到 B 工厂(或者不送),每家工厂一天只能对一张光盘进行操作,同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。

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

输入格式

第一行包含两个整数 n,kn, k,表示有 nn 天,要生产 kk 张光盘。

第二行包含 nn 个整数,第 ii 个整数表示第 ii 天送到 A 工厂加工光盘的花费。

第三行包含 nn 个整数,第 ii 个整数表示第 ii 天送到 B 工厂加工光盘的花费。

输出格式

输出一行一个整数,表示最小花费。

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

样例解释

第一张盘第 11 天在 A 工厂加工,第 11 天在 B 工厂加工。

第二张盘第 22 天在 A 工厂加工,第 44 天在 B 工厂加工。

第三张盘第 33 天在 A 工厂加工,第 55 天在 B 工厂加工。

第四张盘第 66 天在 A 工厂加工,第 88 天在 B 工厂加工。

数据范围

对于所有数据,保证 1kn5×105,1 \leqslant k \leqslant n \leqslant 5 \times 10^5, 1ai,bi1091 \leqslant a_i, b_i \leqslant 10^9