URI Online Judge | 2480

Red Lights

By Lucas Bucior, URI Online Judge BR Brazil

Timelimit: 1

This year Santa Claus gave a very unusual order to Chancellor Jack Redd, who arranges the lamps to be sent to all venues. Noel wants them to be organized in a specific way and it seems that it is not a very simple task for Jack, who really needs your help.

The central lamp distribution unit is located in the south of Brazil, more precisely in Erechim. Jack wants to organize the stock of lights to distribute to the host cities. The stock of lights is large. There are many light boxes with different types: R-Red, W-White, G-Green, S-Silver.

Jack wants you to arrange the columns of boxes according to the colors. First the red ones, then the white ones, followed by the green ones and finally the silver ones. Also, Jack wants the larger boxes to be underneath. The size of the box is represented by the number. For example 8R means a red box of size 8. You can see in the figure below the first highlighted column, already ordered in the form that Jack wants. This image represents the first test case of this problem.

When we move a box, the corresponding line of this light box changes with it (the image shows that all lines are linked by a wire). But there is a small detail! When the first column is ordered according to the criterion established by Jack, it is then removed and its wire is cut. The process starts again with the next column (the one with 6R at the top) is repeated until there are no more columns to sort.

Can you help Jack in this task by indicating how many cash movements are needed to make this organization desired by Noel?


The first line of each instance contains two integers N (1 ≤ N ≤ 20) e M (1 ≤ M ≤ 105), which correspond to the number of rows and columns in stock. The N lines below contain M light boxes, defined as [Q]T. Q (1 ≤ Q ≤ 109) matches the number of lights and T light type R, W, G or S respectively. The entry ends with end-of-file (EOF).


For each instance, print the message "Instance H:", where H is the instance number, sequential and increasing (from 01 to 99). Then print the result of the operations of moving the shelves and the total number of red lights found in the stock. Print a blank line between two consecutive instances.

Exemplo de Entrada Exemplo de Saída

6 5
[6]W [5]S [8]R [5]R [6]R
[8]R [8]G [1]W [7]W [7]R
[7]S [6]W [7]G [2]G [2]W
[5]G [7]G [5]R [7]R [6]R
[2]S [6]R [4]S [5]S [6]S
[7]R [8]W [6]W [8]S [7]R

3 3

[2]R [5]S [7]R
[2]S [8]G [1]W
[1]R [6]W [7]G

7 4
[8]W [5]S [9]R [7]R
[7]R [8]G [1]W [7]W
[7]S [6]W [7]G [2]G
[7]G [6]G [5]R [8]R
[6]S [6]R [4]S [5]S
[5]R [8]W [6]W [8]S
[2]W [5]S [7]R [7]S

Instance 01:

40 72

Instance 02:

7 10

Instance 03:

50 54