Background

Translated from Problem L of NERC 2018。

Problem Description

There are $n$ people in a city and $k$ types of jobs. Each person currently has a job $a_i$. Unfortunately, because some jobs are vacant, the city cannot continue to function normally.

As the ruler of the city, you do not want to see this happen. You decide to persuade some people so that every job has at least one person doing it. For each person $i$, you need to spend $b_i$ time to persuade them.

You need to find the minimum total time you have to spend on persuading.

Input Format

The first line contains two integers $n$ and $k$ $(1 \leq k \leq n \leq 10^5)$, representing $n$ people and $k$ types of jobs.

The second line contains $n$ integers $a_i$ $(1 \leq a_i \leq k)$, where $a_i$ is the job currently done by person $i$.

The third line contains $n$ integers $b_i$ $(1 \leq b_i \leq 10^9)$, where $b_i$ is the time needed to persuade person $i$ to do a different job.

Output Format

Output the minimum total time needed to persuade the citizens.

8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2

10

3 3
3 1 2
5 3 4

0

Hint

For all testdata, it is guaranteed that $1 \leq k \leq n \leq 10^5$, $1 \leq a_i \leq k$, and $1 \leq b_i \leq 10^9$.

For Sample 1, let citizens $1$, $6$, and $8$ take jobs $2$, $4$, and $6$, respectively.

Translated by ChatGPT 5