Cidoai的可乐
题号:NC284972
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Cidoai 喜欢可乐。
它有 n 个点,每个点都有点权 a_i 和一个度数限制 d_i。它想将它们连成一棵树,其中一条边的边权为它的两个端点的点权较小值。它希望这棵树中,所有点的度数都不大于度数限制,且边权和最小。你需要输出这个边权和。

输入描述:

第一行一个正整数 n 表示点数。

第二行 n 个数,依次表示 a_1,a_2,\cdots,a_n

第三行 n 个数,依次表示 d_1,d_2,\cdots,d_n

1 \le n \le 10^5,1 \le a_i \le 10^9,1 \le d_i \le n-1,保证 \sum d_i \ge 2(n-1)

输出描述:

一行一个整数表示答案。
示例1

输入

复制
5
1 2 2 1 1
3 4 2 1 3

输出

复制
4
示例2

输入

复制
5
1 2 3 4 5
1 2 1 3 4

输出

复制
8