Maximum Edge Value Sum in a Tree with Prescribed Degrees

You are given an integer n and two arrays of n integers: a and b. The task is to construct a tree (i.e. a connected acyclic graph) with n nodes satisfying the following conditions:

• The tree has exactly n nodes.
• The degree of the i-th node is exactly a_i.

Each node i is assigned a weight b_i. For any edge connecting nodes i and j, its value is defined as:

Your goal is to design any tree satisfying the degree requirements so that the sum of the values of all edges is maximized. It is guaranteed that there exists at least one tree with the given degree sequence (i.e. \(\sum_{i=1}^{n} a_i = 2(n-1)\)).

Note: You only need to output the maximum possible total value.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(n\) \((2 \le n \le 10^5)\), the number of nodes.
2. The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\), where \(a_i\) is the required degree of node i.
3. The third line contains \(n\) space‐separated integers \(b_1, b_2, \dots, b_n\), where \(b_i\) is the weight of node i.

It is guaranteed that \(\sum_{i=1}^{n} a_i = 2(n-1)\).

outputFormat

Output a single integer, which is the maximum possible sum of the values of the edges in a tree satisfying the given conditions. In other words, if the tree has edges \(E\), you need to maximize:

sample

3
1 1 2
1 2 3

9