Page not loading? Try clicking here.
Placeholder

#9649

Colorful Tower of Hanoi 1s 128MB

Problems

This problem is a variant of the well-known Tower of Hanoi problem.

The Tower of Hanoi problem can be described as follows. There are three rods, say, rod-1, rod-2, and rod-3. On rod-1, n disks of different sizes are stacked in decreasing order. That is, the smallest disk is at the top and the largest is at the bottom. The goal of the problem is to move all the disks stacked on rod-1 to rod-3. However, during the transfer process, only one disk can be moved from on rod to another at a time, and a disk must not be placed on top of a smaller one.

The original problem is changed as follows.

  1. Disks of the same size are allowed. Therefore, in the process of moving disks, a disk can be placed on top of a disk of the same size or larger.
  2. Each disk is painted in one of three colors: red, green, or blue. However, disks of the same size are painted in the same color.
  3. If there are two or more disks of the same size, the relative order between them may be maintained or reversed after moving the disks, which is determined by the disk color. That is, if the disk color is red, the relative order of disks of the same size should be reversed after all disks are finally moved. If the color of the disk is blue, the relative order must be the same as the initial order. And if the color is green, the relative order after movement is not important. However, it is not necessary to satisfy the condition for the relative order in the intermediate process of moving the disks.
  4. The total number of disk moves should be minimized.

Figure C.1 shows an example which satisfies the conditions of relative order depending on the colors after moving all the disks from rod-1 to rod-3.

Figure C.1


Input

Your program is to read from standard input. The input starts with a line containing an integer m (1 \le m \le 25), where m indicates the largest diameter of disks. For each disk of size 1 to m, the disk information is given in turn in the following m lines. More specifically, the i-th (1 \le i \le m) line contains an upper-case character and an integer k (\ge 1), which indicate the color and the number of the disks with diameter i, respectively. The character to specify the color is either ‘R’ for red, ‘G’ for green, or ‘B’ for blue. Note that for each size of 1 to m, there is at least one disk with that size.

Note that the total number of disks is no more than 50.


Output

Your program is to write to standard output. Print exactly one line. The line should contain the minimum number of moves to move all the disks initially stacked on rod-1 to rod-3 satisfying the conditions on relative order depending on colors.


Example #1

2

R 1

B 3
9

Example #2

3

G 1

B 2

R 3
11

Example #3

5

G 2

R 3

R 2

G 3

B 3
120

Source

Seoul Nationalwide Internet Competition 2021 C

You must sign in to write code.