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-----

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-----

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


-----Examples-----
Input
5
3 7 9 7 8
5 2 5 7 5

Output
6

Input
5
1 2 3 4 5
1 1 1 1 1

Output
0



-----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.

Difficulty: interview

Starter code:

Solutions:
import sys
from heapq import heappush, heappop

n = int(input())
a = list(map(int, input().split()))

count = {}

for x in a:
	if x in count:
		count[x] = count[x] + 1
	else:
		count[x] = 1

count = sorted(list(count.items()))
#print(count)

cost= list(map(int, input().split()))
max_cost = max(cost)

a = list(zip(a, cost))
a = sorted(a)
priority = list([max_cost - x for x in [x[1] for x in a]])
a = list(zip(priority, a))

i = 0
queue = []
queue_cost = 0
result = 0

#print(a)

for j in range(len(count)):
	x, c = count[j]
	#print('x = ', x)
	while i < len(a) and a[i][1][0] == x:
		queue_cost += a[i][1][1]
		heappush(queue, a[i])
		i += 1

	#print('queue = ', queue)
	y = x
	while len(queue) > 0 and (j == len(count) - 1 or count[j + 1][0] != y):
		popped = heappop(queue)
		#print(popped, queue)
		queue_cost -= popped[1][1]
		#print(queue_cost)
		result += queue_cost
		y += 1

# while len(queue) > 0:
# 	popped = heappop(queue)
# 	queue_cost -= popped[1][1]
# 	result += queue_cost

print(result)


from heapq import *
n = int(input())
_a = list(map(int, input().split(" ")))
_t = list(map(int, input().split(" ")))
at = [[0, 0]]
for i in range(n):
    at.append([_a[i], _t[i]])
at.append([int(1e11), 0])
at.sort()

def __starting_point():
    Q = []
    s = 0
    cost  = 0
    for i in range(1, n+2):
        a = at[i-1]
        b = at[i]
        num = a[0]
        while len(Q) > 0 and num < b[0]:
            s += heappop(Q)
            num += 1
            cost += s
        s += b[1]
        heappush(Q, -b[1])
        #print("{}, {}, {}".format(i, s, cost))
    print(cost)

__starting_point()

import sys
import heapq
from collections import defaultdict
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
cost=list(map(int,sys.stdin.readline().split()))
for i in range(n):
    arr[i]=[arr[i],cost[i]]
arr.sort()
l=[]
heapq.heapify(l)
prev=0
ans=0
s=0
#print(arr,'arr')
for i in range(n):
    #print(l,'l',s,ans)
    while l and prev<arr[i][0]:
        s-=(l[0])
        ans+=(-s)
        prev+=1
        heapq.heappop(l)
    prev=arr[i][0]
    s+=(-arr[i][1])
    heapq.heappush(l,-arr[i][1])
while l:
    s-=(l[0])
    ans+=(-s)
    heapq.heappop(l)
print(ans)


#!python3
"""
Author: w1ld [at] inbox [dot] ru
"""

from collections import deque, Counter
import array
from itertools import combinations, permutations
from math import sqrt
from heapq import heappush as push, heappop as pop
# import unittest


def read_int():
    return int(input().strip())


def read_int_array():
    return [int(i) for i in input().strip().split(' ')]

######################################################

n = read_int()
a = read_int_array()
t = read_int_array()
srt = list(sorted((a[i], t[i]) for i in range(n)))
cnt = [(-srt[0][1], 0)]
i = 1
cntValue = srt[0][0]
ans = 0
while cnt or i < n:
    if i < n and srt[i][0] == cntValue:
        push(cnt, (-srt[i][1], i))
        i += 1
    elif any(cnt):
        ti, inx = pop(cnt)
        ti = -ti
        ans += (cntValue - srt[inx][0]) * ti
        cntValue += 1
    else:
        cntValue = srt[i][0]
print(ans)







import heapq
h = []
n = int(input())
a = [int(x) for x in input().strip().split()]
t = [int(x) for x in input().strip().split()]
for i in range(len(t)):
    a[i] = [a[i], t[i]]
a.sort(key = lambda x: (x[0], -x[1]))
prev, i, ans= a[0][0], 1, 0
#print(a)
while(i<len(a)):
    #print(prev, ans, h)
    if h:
        if a[i][0] == prev:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            i += 1
        elif a[i][0] == prev+1:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            p = heapq.heappop(h)
            ans += (-p[0]*(prev + 1 - p[1]))
            prev = prev+1
            i += 1
        else:
            p = heapq.heappop(h)
            ans += (-p[0]*(prev + 1 - p[1]))
            prev = prev+1
    else:
        if a[i][0] != prev:
            prev = a[i][0]
            i+=1
        else:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            i+=1
while h:
    p = heapq.heappop(h)
    ans += (-p[0]*(prev + 1 - p[1]))
    prev = prev+1
print(ans)
    


import sys
input = sys.stdin.readline
import heapq
h = []
n = int(input())
a = [int(x) for x in input().strip().split()]
t = [int(x) for x in input().strip().split()]
for i in range(len(t)):
    a[i] = [a[i], t[i]]
a.sort(key = lambda x: (x[0], -x[1]))
prev, i, ans= a[0][0], 1, 0
#print(a)
while(i<len(a)):
    #print(prev, ans, h)
    if h:
        if a[i][0] == prev:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            i += 1
        elif a[i][0] == prev+1:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            p = heapq.heappop(h)
            ans += (-p[0]*(prev + 1 - p[1]))
            prev = prev+1
            i += 1
        else:
            p = heapq.heappop(h)
            ans += (-p[0]*(prev + 1 - p[1]))
            prev = prev+1
    else:
        if a[i][0] != prev:
            prev = a[i][0]
            i+=1
        else:
            heapq.heappush(h, [-a[i][1], a[i][0]])
            i+=1
while h:
    p = heapq.heappop(h)
    ans += (-p[0]*(prev + 1 - p[1]))
    prev = prev+1
print(ans)
    


# n = int(input())
# a = [int(i) for i in input().split(' ')]
# t = [int(i) for i in input().split(' ')]
#
# import collections
# from heapq import heapify, heappop, heappush
#
#
# l = collections.defaultdict(list)
# at = [[a[i], t[i]] for i in range(n)]
# at.sort(key = lambda x: x[0])
# for aa, tt in at:
#     l[aa].append(tt)
#
# for k in l.keys():
#     heapify(l[k])
#
#
# # print(at)
# # print(l)
# res = 0
#
# # tmp = []
#
# q = sorted(l.keys())[::-1]
# while q:
#     i = q.pop()
#     # print("i", i, l[i])
#     # l[i].extend(tmp)
#     if len(l[i]) == 1:
#         continue
#     else:
#         tmp = sorted(l[i])
#         sums = sum(tmp)
#         # res += sums - maxx # leave the one with max time and increase all other by 1, cost their time
#         idx = i
#         while tmp and ((q and idx + 1 != q[-1]) or not q):
#             # print(i, idx, q, tmp)
#             p = tmp.pop()
#             res += sums - p
#             sums -= p
#             idx += 1
#         if tmp:
#             p = tmp.pop()
#             res += sums - p
#             sums -= p
#             l[idx+1].extend(tmp)
#             if not q:
#                 q.append(idx+1)
# print(res)
#
#
#
#
#
#
#


import sys

inp = sys.stdin.readline
input = lambda: inp().strip()


# flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())


def lin(): return list(map(int, input().split()))


def main():
    import heapq as hq
    n = iin()
    a = lin()
    t = lin()
    dc = {}
    for i in range(n):
        try:
            dc[a[i]].append(t[i])
        except:
            dc[a[i]] = [t[i], ]
    # print(dc)
    sa = list(dc.keys())
    sa.sort()
    n = len(sa)
    ch = 0
    pt = sa[ch]
    temp = []
    sm = 0
    ans = 0
    hq.heapify(temp)
    done = 0
    while ch < n:
        # print(temp, sa[ch])
        pt = sa[ch]
        if len(dc[pt]) > 1 or done:
            a1 = sorted(dc[pt])
            for item in a1:
                hq.heappush(temp, -item)
                sm += item
            x = hq.heappop(temp) * (-1)
            dc[pt] = [x]
            sm -= x
            while len(temp):
                # print('A', ch, pt, temp )
                ans += sm
                pt += 1
                if pt in dc:
                    ch += 1
                    done = 1
                    break
                else:
                    x = hq.heappop(temp) * (-1)
                    sm -= x
            else:
                done = 0
        else:
            ch += 1
            done = 0
    # print(dc)
    print(ans)

main()


n = int(input())
a = [int(i) for i in input().split(' ')]
t = [int(i) for i in input().split(' ')]

import collections
from heapq import heapify, heappop, heappush


l = collections.defaultdict(list)
at = [[a[i], t[i]] for i in range(n)]
at.sort(key = lambda x: x[0])
for aa, tt in at:
    l[aa].append(tt)



# print(at)
# print(l)
res = 0

# tmp = []

q = sorted(l.keys())[::-1]
tmp = []
heapify(tmp)
sums = 0
while q:

    i = q.pop()
    if len(l[i]) == 1 and not tmp:
        continue
    else:
        for ll in l[i]:
            heappush(tmp, -ll)
            sums += ll
        idx = i
        # print(i, idx, q, tmp, sums)
        while tmp and ((q and idx + 1 != q[-1]) or not q):
            # print(i, idx, q, tmp)
            p = -heappop(tmp)
            res += sums - p # leave the one with max time and increase all other by 1, cost their time
            sums -= p
            idx += 1
        if tmp:
            # print('tmp', i, tmp)
            p = -heappop(tmp)
            res += sums - p
            sums -= p
            # print(res, p)
            # l[idx+1].extend(tmp)
            if not q:
                q.append(idx+1)
print(res)









# import sys
#
# inp = sys.stdin.readline
# input = lambda: inp().strip()
#
#
# # flush= sys.stdout.flush
# # import threading
# # sys.setrecursionlimit(10**6)
# # threading.stack_size(2**26)
#
# def iin(): return int(input())
#
#
# def lin(): return list(map(int, input().split()))
#
#
# def main():
#     import heapq as hq
#     n = iin()
#     a = lin()
#     t = lin()
#     dc = {}
#     for i in range(n):
#         try:
#             dc[a[i]].append(t[i])
#         except:
#             dc[a[i]] = [t[i], ]
#     # print(dc)
#     sa = list(dc.keys())
#     sa.sort()
#     n = len(sa)
#     ch = 0
#     pt = sa[ch]
#     temp = []
#     sm = 0
#     ans = 0
#     hq.heapify(temp)
#     done = 0
#     while ch < n:
#         # print(temp, sa[ch])
#         pt = sa[ch]
#         if len(dc[pt]) > 1 or done:
#             a1 = sorted(dc[pt])
#             for item in a1:
#                 hq.heappush(temp, -item)
#                 sm += item
#             x = hq.heappop(temp) * (-1)
#             dc[pt] = [x]
#             sm -= x
#             while len(temp):
#                 # print('A', ch, pt, temp )
#                 ans += sm
#                 pt += 1
#                 if pt in dc:
#                     ch += 1
#                     done = 1
#                     break
#                 else:
#                     x = hq.heappop(temp) * (-1)
#                     sm -= x
#             else:
#                 done = 0
#         else:
#             ch += 1
#             done = 0
#     # print(dc)
#     print(ans)
#
# main()