← 返回题目列表

Codeforces · 1310/A

A. 建议

中文机器翻译题面 查看原题

VK新闻推荐系统每天为每个用户选择$$$n$$$不相交类别之一的有趣出版物。每份出版物都属于一个类别。对于每个类别 $$$i$$$ 批处理算法选择 $$$a_i$$$ 出版物。

最新的 A/B 测试表明,如果每个类别在每日推荐中包含不同数量的出版物,则用户会更积极地阅读推荐的出版物。目标算法可以在 $$$t_i$$$ 秒内找到第 $$$i$$$ 个类别的单个有趣出版物。

将发布添加到批处理算法执行结果中所需的最短总时间是多少,以便所有类别都有不同数量的发布?您无法删除批处理算法推荐的发布。

输入

输入的第一行由单个整数 $$$n$$$ 组成 - 新闻类别的数量 ($$$1 \le n \le 200\,000$$$)。

输入的第二行由 $$$n$$$ 整数 $$$a_i$$$ 组成 - 由批处理算法选择的第 $$$i$$$ 类别的出版物数量 ($$$1 \le a_i \le 10^9$$$)。

输入的第三行由 $$$n$$$ 整数 $$$t_i$$$ 组成 - 目标算法找到类别 $$$i$$$ 的一个新出版物所需的时间 ($$$1 \le t_i \le 10^5)$$$。

输出

打印一个整数——目标算法消除相同大小的类别所需的最短时间。

示例

输入 #1

5
3 7 9 7 8
5 2 5 7 5

输出 #1

6

输入 #2

5
1 2 3 4 5
1 1 1 1 1

输出 #2

0

注意

在第一个示例中,可以找到三个第二类型的出版物,这将需要 6 秒。

在第二个示例中,所有新闻类别都包含不同数量的出版物。