Dr. Strange finally discovered a safe way to travel between parallel universes. By noticing people’s interests, he decided to start a courier business between two parallel universes named and . There are habitable planets in both and numbered from to . For each , from to , let’s call planet for universe and for universe .
Dr. Strange appointed agents numbered from to . For universe , each planet will host exactly one agent. And each agent will be appointed to exactly one planet. The same goes for universe . So, for each from to , the agent will be appointed to exactly one planet from universe and one planet from universe .
Dr. Strange initially created some routes between universes and . For each , there will be a direct route between and . For each , the agent is appointed on one planet from and one planet from . These two planets are connected through a direct route. Using these routes, one planet may or may not get connected to many other planets using a series of routes.
Now Dr. Strange wants each planet to be connected to all other planets using one or more routes. Now, he may need to create some new routes. For each , planets and have a price tag . Amount needs to be paid if he wants to create a route and connect or with that route. For example, if he wants to create a route between and , he has to pay amount of money.
What is the minimum amount of money that needs to spent, if he wants to make all the planets connected?
The first line on input will consist of an integer .
The second line will consist of integers. The integer will represent the agent's identifier that will be appointed on the planet .
The next line will consist of N integers. The integer will represent the agent’s identifier that will be appointed on the planet .
The fourth line will consist of integers .
Print one integer, the minimum possible amount of money Dr. Strange has to pay in order to make each planet accessible to all other planets.
Input | Output |
---|---|
4 3 4 1 2 4 3 1 2 4 4 4 4 | 16 |
Dr. Strange can create a route between planets and . Then another route between planets and . So, he needs to pay amount to planet , amount to planet , and amount to planet . |