Santa has visited, and you have found a new video game under your Christmas tree!
In this video game, the player attempts to collect stars scattered around the game world. After collecting a single star, they return to the starting location until all stars have been collected. Moving around requires various manipulating various buttons on the controller, including the A button. What is the minimum number of times the A button must be pressed in order to collect all the stars and beat the game?
The game world consists of locations numbered from to . There are stars at location . Location is the starting location where the player starts the game, and are returned to after collecting a star. There are known techniques for going from one location to another, these are numbered from to . The -th of these techniques is for going from location to location . These techniques each have different requirements regarding the A button that will be specified in more detail later.
The A button has two state: pressed, and unpressed. Initially, the button is unpressed. Going from the unpressed state to the pressed state is called "pressing the A button". The number of these A presses is the quantity we want to minimize. Note that once the A button is pressed, it does not need to be released right away. The A button can continue to be held even while collecting a star and returning to the starting location.
Each technique has a type which is either
Atechniques require performing an additional A presses.
Btechniques require performing an additional A presses under the condition that the A button is already being held (in real-life applications, this extra requirement is known as a "half" A press).
Ctechniques simply require the A button to be in the unpressed state.
Note that the A button can be manipulated even outside of these techniques - while at one of the locations the button can be pressed or released at any time.
It is guaranteed that it is possible to collect all the stars.
Subtask 1 [50%]
There are no type
Subtask 2 [50%]
No additional specifications.
The first line contains two space-separated integers and .
The next line contains space-separated integers .
The next lines first contain , , and .
B, then the line also contains .
Output a single integer, the minimum number of A presses needed for collecting all stars.
3 3 0 0 5 1 2 B 0 2 3 C 1 3 A 1
Output for Sample Input
Explanation for Sample Input
First, press the A button to travel from 1 to 3 and keep it down. After collecting a star, you are returned to 1 with the A button down. The B technique can then be used to travel to 2. Letting go of the A button allows the C technique, which moves you to 3 and after collecting a second star, back to 1. Repeating this process twice lets you go to 3 enough times to collect all the stars. In total, 3 button presses are made.