Your friends asked you to go out on a Friday night, but you had a much better idea of enjoying a new game you bought. The game is Monster Battle for the Gamegirl Colour, and you're really hyped to get into it! Before playing, you're thinking of making a program to optimise all the battles in the game, so you'll never have to feel the pain of losing and restarting.

In this game, you and your opponent both have ~n~ monsters. Each monster has some strength value ~a_i~, and a type (fire, water, or grass). You match up your monsters with your opponent's in pairs, and let each pair battle until a victor or tie is determined.

In each battle, the monster with the higher strength wins. However, water is strong against fire, fire is strong against grass, and grass is strong against water. If a monster is battling a monster with a type it is strong against, its strength is effectively doubled for that battle.

How many battles can you win with the optimal pairing? Don't count ties in your answer.

Input

The first line consists of a single integer ~n\ (1 \leq n \leq 4000)~, the number of monsters on both your and your opponent's teams.

The next two lines both consist of ~n~ pairs of characters and integers, separated by spaces, where each pair represents a single monster. The top line represents your monsters, while the bottom line represents your opponent's monsters. The character is either 'W', 'F', or 'G', and represents the type of that monster. The integer is ~a_i\ (1 \leq a_i \leq 10^6)~, the strength of that monster.

Output

Output the maximum number of battles you can win as a single integer, not counting ties.

Example

Input 1

4
F 3 F 2 G 9 W 8
G 3 G 8 F 15 G 2

Output 1

4

It is possible to win all 4 battles in this case:

• Your F3 beats their G3 as it is super effective.
• Your F2 beats their G2.
• Your G9 beats their G8.
• Your W8 beats their F15.

Input 2

3
W 4 F 3 G 1
F 2 W 3 W 2

Output 2

2

In this case, it is impossible to win all 3 battles. There are multiple pairings to beat 2, but one of them is:

• Your W4 beats their W3
• Your F3 beats their F2
• Your G1 ties with their W2

Input 3

2
F 5 W 3
G 10 F 6

Output 3

0

In this case all our monsters either lose or tie to all theirs. The best possible result is 2 ties, but we only care about wins so this doesn't matter.