You finally get into the casino, and the first thing you need to do is buy chips. You approach the machine and buy ~n~ white chips, but then notice something strange. The machine will let you convert between different kinds of chips at different rates. For example:

• ~1~ white chip ~\rightarrow 2~ red chips
• ~1~ red chip ~\rightarrow 3~ blue chips
• ~1~ blue chip ~\rightarrow 1~ white chip

Something strikes you as odd about these exchange rates. They're not fair! In the above example, starting with ~10~ white chips:

• Convert them all to red chips. You how have ~20~ red chips.
• Convert them all to blue chips. You now have ~60~ blue chips.
• Convert them all to white chips. You now have ~60~ white chips.

And now, you've ended up with ~6~ times more than your starting number of white chips!

However, the people behind you in line are impatient, and will only let you make at most ~m~ exchanges. What is the maximum number of white chips you can get from these exchanges?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 100)~, the number of white chips you start with.

The second line consists of an integer ~m~ ~(1 \leq m \leq 10)~, the number of exchanges you are allowed to make.

The third line consists of an integer ~k~ ~(1 \leq k \leq 100)~, the number of types of exchanges that the machine offers.

The next ~k~ lines contain ~S_a~, ~x_b~, and ~S_b~, meaning that one ~S_a~ chip is equivalent to ~x_b~ ~S_b~ chips. The strings ~S_a~ and ~S_b~ ~(1 \leq S_i.\text{length} \leq 10)~ are the names of the chips, while ~x_b~ ~(1 \leq x_i \leq 10)~ is an integer representing the conversion rate.

Output

Output the maximum number of white chips you can make from these exchanges, rounded down to the nearest chip.

Clarifications

• Exchanges are offered only unidirectionally.
• No exchanges will be for a chip and itself.
• You must end up with white chips at the end of your exchanges.
• You don't need to use all your exchanges.

Example

Input

10
3
3
White 2 Red
Red 3 Blue
Blue 1 White

Output

60

This is simply the example above. ~60~ is the maximum number of white chips you can get within the allowed ~3~ exchanges.

Input

1
7
5
White 2 Red
Red 2 Blue
Blue 2 White
Red 3 Green
Green 2 Blue

Output

192

Convert:

• White to red = ~2~ red chips
• Red to green = ~6~ green chips
• Green to blue = ~12~ blue chips
• Blue to white = ~24~ white chips
• White to red = ~48~ red chips
• Red to blue = ~96~ blue chips
• Blue to white = ~192~ white chips

This is the maximum number of chips you can obtain with ~7~ exchanges.

Input

100
10
2
Red 2 Blue
Blue 2 White

Output

100

You can't convert your white chips to anything else, so you are stuck with ~100~.