Given $N$ shadows of memory, initially they are messy and distorted.
For each $i$, it is given that the memory indexed $i$ was formed at the $T_i$-th moment.
Your goal is to sort the memories chronologically (i.e. sort in ascending order of $T_i$).
To do this, you may use a memory restoring machine:
you can pay a cost of $\min(C_x, C_y)$ to swap the positions of memories indexed $x$ and $y$.
(Note that the indexes of the memories stay with the memory itself, not the position; for more details, you may look at the sample explanation.)
Find the minimum cost to restore the memories back in order.
Input
On line $1$, an integer $N$.
On line $2$, $N$ integers $T_1, T_2, \dots, T_N$.
On line $3$, $N$ integers $C_1, C_2, \dots, C_N$.
Output
One integer, the minimum cost to restore the memories back in order.
Constraints
In all cases,
$1 \le N \le 10^6$
$T$ is a permutation of $1$ to $N$.
$1 \le C_i \le 10^9$
Subtask $1$: $N \le 3$ ($16$ points)
Subtask $2$: All $C_i$ are the same, $N \le 500$ ($21$ points)
Subtask $3$: All $C_i$ are the same ($26$ points)
Subtask $4$: $10^9-5 \le C_i \le 10^9$ ($23$ points)
Subtask $5$: No Additional Constraints ($14$ points)
Sample Test Cases
| Input | Output | |
|---|---|---|
| 4 1 4 2 3 5 5 5 5 |
10 | |
Initially $T$ is 1,4,2,3 First swap memories with index 2 and 3, the cost is $min(C_2,C_3)=5$ Now $T$ is 1,2,4,3 Then swap memories with index 2 and 4, the cost is $min(C_2,C_4)=5$ Now $T$ is 1,2,3,4 It can be shown that 10 is the minimum cost to sort $T$ in ascending order. |
||
| 4 1 4 2 3 1 5 5 5 |
4 | |
Initially $T$ is 1,4,2,3 First swap memories with index 1 and 2, the cost is $min(C_1,C_2)=1$ Now $T$ is 4,1,2,3 Then swap memories with index 1 and 3, the cost is $min(C_1,C_3)=1$ Now $T$ is 4,2,1,3 Then swap memories with index 1 and 4, the cost is $min(C_1,C_4)=1$ Now $T$ is 4,2,3,1 Then swap memories with index 1 and 2, the cost is $min(C_1,C_2)=1$ Now $T$ is 1,2,3,4 It can be shown that 4 is the minimum cost to sort $T$ in ascending order. |
||
Scoring: Per Subtask
Authored by s23f32
Appeared in WYOI Round 1 [APIO & TFT Practice]