[AdditionalFile5649.zip](file://AdditionalFile5649.zip?type=additional_file)

#5649. 「PA 2014 Final」Żarówki

标签: 传统 | 时间限制: 2500 ms | 内存限制: 64 MiB |

题目描述

题目译自 PA 2014 Final Zadanie

Bajtazar 新家的装修工作即将结束。剩下的工作只有在 $n$ 个房间中各拧入一个灯泡。对于每个房间，他都确定了能充分照明该房间所需的最小灯泡功率。

Bajtazar 已经买了 $n$ 个灯泡，但现在他发现这些灯泡并不完全符合他的预期。可能无法为所有房间提供充足照明，或者某些灯泡的功率大得没必要。因此，Bajtazar 决定去商店更换一些灯泡，以便能够充分照明所有房间，同时尽可能降低灯泡的总功率。商店可以提供任何正整数功率的灯泡。Bajtazar 的背包最多能装下 $k$ 个灯泡去换成新的，这是他愿意更换的灯泡的最大数量。

请帮助 Bajtazar 选择哪些灯泡需要更换，使得所有房间都能得到充足照明，同时使所有灯泡的总功率达到最小。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(1 \leq k \leq n \leq 500000)$，分别表示房间的数量（也是灯泡的数量）以及拜塔扎尔背包能装下的灯泡数量。房间编号从 $1$ 到 $n$。

第二行包含 $n$ 个整数 $p_{1}, p_{2}, \ldots, p_{n}$ $(1 \leq p_{i} \leq 10^{9})$，表示拜塔扎尔目前拥有的灯泡功率。

第三行包含 $n$ 个整数 $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 10^{9})$，表示各个房间的照明要求。即在第 $i$ 个房间必须拧入功率至少为 $w_{i}$ 的灯泡。

输出格式

如果通过更换至多 $k$ 个灯泡无法使所有房间都得到充足照明，则输出 NIE。否则，输出一个整数，表示在更换至多 $k$ 个灯泡后，用于照明房屋的所有灯泡的最小总功率。

样例

输入

6 2
12 1 7 5 2 10
1 4 11 4 7 5

输出

33

只需将功率为 $2$ 的灯泡更换为功率为 $11$ 的灯泡，并将功率为 $10$ 的灯泡更换为功率为 $1$ 的灯泡即可。这样，几乎所有的房间都会拧入功率恰好等于最小要求的灯泡。唯一的例外是一个只需用功率为 $11$ 的灯泡照明的房间，它将被拧入一个功率为 $12$ 的灯泡。