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 秒。
在第二个示例中,所有新闻类别都包含不同数量的出版物。