Make Array Elements Distinct with Minimum Cost

You are given two integer sequences of length n: an array a and an array b.

You can perform the following operation any number of times:

• Increase an element a[i] by 1 at a cost of b[i].

Your goal is to make all the elements in array a distinct (i.e. no two elements are equal) while minimizing the total cost. However, before you start modifying the array, you are allowed to perform an unlimited number of operations to swap any two elements in array b (i.e. swap b[i] and b[j] for any 1 ≤ i, j ≤ n). This means you can arbitrarily reassign the cost multipliers among the indices.

Because the answer can be large, output the answer modulo \(2^{64}\) (i.e. 18446744073709551616).

Hints:

• Since swapping b is free, you can assign the cheaper costs to the indices which require more increments.
• A natural approach is to first sort the array a and then for each consecutive element, force the current element to be at least one more than the previous element. Let the increments required be \(inc[i] = f[i] - a[i]\) where \(f[i]\) is the final value for a[i].
• Once you calculate the required increments, sort these values in descending order, and sort the array b in ascending order. Then, by the rearrangement inequality, the minimum total cost is \(\sum_{i=0}^{n-1} inc_{desc}[i] \times b_{asc}[i]\).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the length of the arrays.

The second line contains n integers, the elements of array a (\(a_i\)).

The third line contains n integers, the elements of array b (\(b_i\)).

outputFormat

Output a single integer, the minimum total cost to make all elements in a distinct, taken modulo \(2^{64}\).

sample

2
1 1
100 1

1