（CodeForces - 557C）Arthur and Table

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.

In total the table Arthur bought has n legs, the length of the i-th leg is li.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number di — the amount of energy that he spends to remove the i-th leg.

A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.

Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.

Input

The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of n integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table.

The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.

Output

Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.

Examples

Input

2

1 5

3 2

Output

2

Input

3

2 4 4

1 1 1

Output

Input

6

2 2 1 1 3 3

4 3 5 5 2 1

Output

8

題目大意：一個有n條腿的桌子，要使最長的那條腿的數量大于總腿數的一半，拆掉第i條腿需要的代價是d[i]，問要使桌子合法所要消耗的最小代價是多少。

思路：我們可以考慮先枚舉桌子最後支撐腿的長度x。因為是支撐腿，意味着所有大于x的腿都要被砍掉。對于支撐腿，顯然全部保留最好。接下來就是按照代價從小到大砍腿。由于代價最多200，可以借鑒桶排思想，将小于x的腿代價放入桶内。從小到大掃一遍桶砍腿直到滿足要求即可即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF=;
const int maxn=;
int num[maxn],bigger[maxn];//num記錄腿長為l的腿數，bigger記錄腿長大于l的代價 
int cost[];//記錄代價為i的有多少條 

struct node
{
    int l,d;
}a[maxn];

bool cmp(node a,node b)
{
    return a.l<b.l;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(num,,sizeof(num));
        memset(bigger,,sizeof(bigger));
        memset(cost,,sizeof(cost));
        for(int i=;i<n;i++) 
        {
            scanf("%d",&a[i].l);
            num[a[i].l]++;
        }
        for(int i=;i<n;i++) scanf("%d",&a[i].d);
        sort(a,a+n,cmp);
        int sum=;
        for(int i=n-;i>;i--)
        {
            sum+=a[i].d;
            if(a[i].l!=a[i-].l) bigger[a[i-].l]=sum;
        }
        int ans=bigger[a[].l];
        cost[a[].d]++;
        for(int i=;i<n;i++)
        {
            if(a[i].l!=a[i-].l)
            {
                int tmp=i-num[a[i].l]+;//需要減掉的腿的數量
                sum=bigger[a[i].l];
                if(tmp>)
                {
                    for(int j=;j<=;j++) //從小到大減去tmp條腿
                        if(cost[j])
                        {
                            if(cost[j]>=tmp)
                            {
                                sum+=j*tmp;
                                tmp=;
                                break;
                            }
                            else
                            {
                                sum+=j*cost[j];
                                tmp-=cost[j];
                            }
                        } 
                } 
                ans=min(ans,sum);
            }
            cost[a[i].d]++;
        }
        printf("%d\n",ans);     
    }
    return ;
}