C - Move It Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1 から N の番号がついた N 個の箱と 1 から N の番号がついた N 個の荷物があります。荷物 i (1 \leq i \leq N) は箱 A_i の中にあり、重さは W_i です。

あなたは荷物を一つ選び、他の箱の中に移動させる操作を 0 回以上繰り返し行うことができます。1 回の操作で移動させる荷物の重さが w であるとき、w のコストがかかります。

全ての箱に荷物が 1 つずつ入っている状態にするためにかかるコストの総和の最小値を求めてください。

制約

  • 1 \leq N \leq 10^{5}
  • 1 \leq A_i \leq N (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N
W_1 W_2 \ldots W_N

出力

全ての箱に荷物が 1 つずつ入っている状態にするためにかかるコストの総和の最小値を出力せよ。

入力例 1

5
2 2 3 3 5
33 40 2 12 16

出力例 1

35

以下の 2 回の荷物の移動で、すべての箱に荷物が 1 つずつ入っている状態にすることができます。

  • 荷物 1 を箱 2 から箱 1 に移す。このとき、コストは 33 である。
  • 荷物 3 を箱 3 から箱 4 に移す。このとき、コストは 2 である。

この 2 回の荷物の移動は合計 35 のコストかかります。 35 未満のコストですべての箱に荷物が 1 つずつ入っている状態にすることはできないため、 35 を出力します。

入力例 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

出力例 2

17254

Score : 250 points

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

  • 1 \leq N \leq 10^{5}
  • 1 \leq A_i \leq N (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
W_1 W_2 \ldots W_N

Output

Print the minimum total cost required to make each box contain exactly one item.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

  • Move item 1 from box 2 to box 1. The cost is 33.
  • Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

17254