Lazyland
InterviewTime limit2sMemory limit512 MB
Each of n workers wants one of k jobs and costs b_i to reassign. Keep one worker per chosen job and reassign the cheapest extras to cover every missing job. Return the minimum total cost.
Problem
The kingdom of Lazyland is home to n idlers. These idlers are incredibly lazy and cause many problems for their ruler, the mighty King of Lazyland.
Today, k important jobs for the kingdom must be performed (k ≤ n). Every job must be done by one person, and every person can do at most one job. The King allowed each idler to choose one job they wanted to do, and the i-th idler chose job ai.
Unfortunately, some jobs may not be chosen by anyone, so the King must persuade some idlers to choose a different job. The King knows that persuading the i-th idler takes bi minutes. He asked his minister of labour to calculate the minimum total time he needs to spend persuading idlers so that all jobs get done. Can you help him?
Input
The first line of input contains two integers n and k (1 ≤ k ≤ n ≤ 105): the number of idlers and the number of jobs.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ k): the job chosen by each idler.
The third line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 109): the time the King needs to spend to persuade the i-th idler.
Output
The only line of output should contain one number: the minimum total time the King needs to spend persuading idlers so that all jobs get done.
Notes
In the first example, the optimal plan is to persuade idlers 1, 6, and 8 to do jobs 2, 4, and 6.
In the second example, every job was chosen by some idler, so there is no need to persuade anyone.