## A Button Challenge

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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 A, B, or C.

• Type A techniques require performing an additional A presses.
• Type B techniques 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).
• Type C techniques 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.

#### Constraints

is either A, B, or C

It is guaranteed that it is possible to collect all the stars.

There are no type C techniques.

#### Input Format

The first line contains two space-separated integers and .

The next line contains space-separated integers .

The next lines first contain , , and . If is A or B, then the line also contains .

#### Output Format

Output a single integer, the minimum number of A presses needed for collecting all stars.

#### Sample Input

3 3
0 0 5
1 2 B 0
2 3 C
1 3 A 1

#### Output for Sample Input

3

#### 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.