Elections

Soon, parliamentary elections will be held in the country of Dadorlandtiria. There are \(n\) voters in total, numbered from \(0\) to \(n-1\). There are also \(k\) candidates, numbered from \(0\) to \(k-1\). Note that the candidates themselves do not vote in the election – there are \(n+k\) people in total.

Komiljon, who has long dreamed of becoming a deputy, has put forward his candidacy. Komiljon's number is \(0\).

According to pre-election data, voter \(i\) intends to vote for candidate \(p[i]\). However, Komiljon can persuade voter \(i\) to vote for him in exchange for \(c[i]\) dador dollars.

To win the election, Komiljon must collect strictly more votes than every other candidate. What is the minimum amount Komiljon must spend to achieve this?

Implementation details

You should implement the following procedure:

int64 min_cost(int n, int k, int[] p, int[] c)

• \(n\): the total number of voters.
• \(k\): the total number of candidates.
• \(p\): an array of length \(n\) – whom each voter intends to vote for.
• \(c\): an array of length \(n\) – the price of buying each voter.
• The procedure should return the minimum amount of money needed to win the election.
• This procedure is called exactly once.

Examples

Consider the following call:

min_cost(7, 3, [1, 2, 0, 2, 2, 1, 1], [3, 4, 9, 9, 8, 1, 2])

So \(n=7\), \(k=3\), \(p = [1, 2, 0, 2, 2, 1, 1]\) and \(c = [3, 4, 9, 9, 8, 1, 2]\).

Komiljon can come to an agreement with voters \(1\) and \(5\). Then he spends \(c[1] + c[5] = 4 + 1 = 5\) dador dollars. Komiljon then receives \(3\) votes, while the other candidates receive \(2\) each.

Consider another example:

min_cost(3, 2, [0, 1, 0], [9, 9, 9])

It can be seen that Komiljon has \(2\) votes while his opponent has \(1\). So there is no need to spend money. The procedure should return \(0\).

Constraints

• \(2 \le n \le 200\,000\)
• \(2 \le k \le n\)
• \(0 \le p[i] \le k-1\) (for all \(0 \le i \le n - 1\))
• \(1 \le c[i] \le 10^9\) (for all \(0 \le i \le n - 1\))

Subtasks

1. (8 points) \(n \le 18\)
2. (12 points) \(n \le 200\)
3. (22 points) \(n \le 2000\)
4. (6 points) \(k = 2\)
5. (10 points) \(k = 3\)
6. (15 points) \(c[i] = 1\)
7. (27 points) No additional constraints.

Sample grader

Feed the sample grader the input in the following format:

• line \(1\): \(n \; k\)
• line \(2\): \(p[0] \; p[1] \; \ldots \; p[n - 1]\)
• line \(3\): \(c[0] \; c[1] \; \ldots \; c[n - 1]\)

The sample grader prints the answer in the following format:

• line \(1\): the answer returned by the min_cost procedure.