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 ≤ n ≤ 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 ≤ a_i ≤ 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 ≤ t_i ≤ 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.
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class CodeForcesD {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int categories = scanner.nextInt();

        Category[] c = new Category[categories];

        for (int i = 0; i < categories; i++) {
            c[i] = new Category(scanner.nextInt(), 0);
        }

        for (int i = 0; i < categories; i++) {
            c[i].priceToAddOne = scanner.nextInt();
        }

        long minRequiredTime = new CodeForcesD().getMinRequiredTime(c);

        System.out.println(minRequiredTime);
    }

    public long getMinRequiredTime(Category[] c) {
        Arrays.sort(c, (f, s) -> {
            long pd = f.publications - s.publications;
            if (pd != 0) {
                return pd < 0 ? - 1 : 1;
            }
            return s.priceToAddOne - f.priceToAddOne;
        });

        Queue<Category> duplicates = new PriorityQueue<>();

        long minRequiredTime = 0;

        for (int i = 1; i < c.length; i++) {
            if (c[i].publications != c[i - 1].publications) {
                long nextFreeSpot = c[i - 1].publications + 1;
                long freeSpots = c[i].publications - nextFreeSpot;
                while (freeSpots > 0 && !duplicates.isEmpty()) {
                    Category toBumpUp = duplicates.poll();
                    minRequiredTime += (nextFreeSpot - toBumpUp.publications) * toBumpUp.priceToAddOne;
                    nextFreeSpot++;
                    freeSpots--;
                }
            }

            if (!duplicates.isEmpty()
                    && duplicates.peek().priceToAddOne > c[i].priceToAddOne
                    && c[i - 1].publications != c[i].publications) {
                Category replace = duplicates.poll();
                duplicates.add(c[i]);

                minRequiredTime += (c[i].publications - replace.publications) * replace.priceToAddOne;

                replace.publications = c[i].publications;
                c[i] = replace;
            } else if (c[i].publications == c[i - 1].publications) {
                duplicates.add(c[i]);
            }
        }

        long nextFreeSpot = c[c.length - 1].publications + 1;
        while (!duplicates.isEmpty()) {
            Category toBumpUp = duplicates.poll();
            minRequiredTime += (nextFreeSpot - toBumpUp.publications) * toBumpUp.priceToAddOne;
            nextFreeSpot++;
        }

        return minRequiredTime;
    }


    public static class Category implements Comparable<Category> {
        long publications;
        int priceToAddOne;

        public Category(long publications, int priceToAddOne) {
            this.publications = publications;
            this.priceToAddOne = priceToAddOne;
        }

        @Override
        public int compareTo(Category o) {
            return o.priceToAddOne - priceToAddOne;
        }
    }
}
