Recommendations
Contest: VK Cup 2019-2020 - Elimination Round (Engine)
Difficulty rating: 1700
Tags: data structures, greedy, sortings

VK news recommendation system daily selects interesting publications of one of $$$n$$$ disjoint categories for each user. Each publication belongs to exactly one category. For each category $$$i$$$ batch algorithm selects $$$a_i$$$ publications.

The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of $$$i$$$-th category within $$$t_i$$$ seconds.

What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm.

Input format:
The first line of input consists of single integer $$$n$$$ — the number of news categories ($$$1 \le n \le 200\,000$$$).

The second line of input consists of $$$n$$$ integers $$$a_i$$$ — the number of publications of $$$i$$$-th category selected by the batch algorithm ($$$1 \le a_i \le 10^9$$$).

The third line of input consists of $$$n$$$ integers $$$t_i$$$ — time it takes for targeted algorithm to find one new publication of category $$$i$$$ ($$$1 \le t_i \le 10^5)$$$.

Output format:
Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, it is possible to find three publications of the second type, which will take 6 seconds.

In the second example, all news categories contain a different number of publications.

Example input:
5
3 7 9 7 8
5 2 5 7 5

Example output:
6

Example input:
5
1 2 3 4 5
1 1 1 1 1

Example output:
0

Editorial:
In this problem we have an array $$$a_1, \ldots, a_n$$$, we can increase each $$$a_i$$$ by one with cost $$$t_i$$$, and we want to make all $$$a_i$$$ different with minimal total cost.
Let's sort $$$a_i$$$ in a non-decreasing way (and permute the $$$t$$$ in a corresponding way). Let's see at the minimal number, $$$a_1$$$. If it is unique, e.g. $$$a_1 \ne a_2$$$, then we don't need to change $$$a_1$$$ — it is already unique, and it can't get equal to something else if we don't increase it. In this case, we can just skip $$$a_1$$$ and solve the smaller problem without $$$a_1$$$.
Otherwise, suppose there is some $$$j>1$$$ such that $$$a_1 = a_2 = \ldots = a_j$$$. Obviously, we should leave at most one of them with the current value, and increase other $$$j-1$$$ numbers by one. Which one should be not increased? We shouldn't increase the $$$a_l$$$ ($$$1 \le l \le j$$$) with the maximal $$$t_l$$$ because it minimizes the total cost. So, we should remove the maximal value $$$t_l$$$ among all elements with minimal $$$a_l$$$, and increase all other by one. This effectively reduces our problem to the smaller one, decreasing $$$n$$$ by one.
This gives us a $$$\mathcal{O}(n^2)$$$ solution — $$$n$$$ times we discard one minimum from the array and increase all other minimums by one. We can further optimize it by using a multiset of values $$$t_l$$$ for all minimal $$$a_l$$$ and its sum. At each iteration, we should (probably) add some values to a multiset, if the number of minimums in array increases, discard one maximum from multiset and add the current sum to the answer. Continue the process until the array becomes empty. This is an $$$\mathcal{O}(n \log n)$$$ solution.