401851: GYM100541 J Math Magic

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Math Magictime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A Math Magic game consists of a number of equal-sized blocks. Each block in Math Magic is divided into 4 triangles where each triangle takes a color from Blue (B), Green (G), Red (R), or Yellow (Y) and an integer from 0 to 9.

Starting with the center block, at each step a player can adjoin a new block in one of four directions along the horizontal or vertical axes centered at the center block. The new block is attached to an existing block in such a way that the two corresponding adjoined triangles must have the same color. The score of each block is calculated based on the color of the adjoined triangle, the integer in the adjoined triangle of the new block and the sum of four integers in the new block as follows:

If a block cannot be added in the board or the player does not wish to include in the board, then its score is S and the block is skipped. Notice that the center block, i.e. the first block, does not have a score. For example, consider the following steps to add a new block and their corresponding scores

S = 4 + 4 + 0 + 1 = 9

x = 4

Color of the adjoined triangle: red

Score = S * x = 9 * 4 = 36

S = 1 + 3 = 4

x = 3

Color of the adjoined triangle: yellow

Score = 4

Given a list of blocks, a player will use the first one as the center block and either add or skip the remaining blocks to the board one at a time in sequence. The blocks can be rotated before being added to the board but they must be considered in the same order as given. Your task is to find the maximum total score a player could get.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 40. The following lines describe the datasets.

The first line of each dataset contains an integer n(n≤250, 000), which is the total number of blocks including the center block as the first one. For the next n lines, each line contains 8 characters representing the colors and integers for the block’s triangle in clockwise order: c1n1c2n2c3n3c4n4 where ci (ci takes values from Y, R, G, or B standing for yellow, red, green or blue respectively), ni (ni takes an integer value from 0 to 9) is the color and integer of the i triangle respectively (1 ≤ i ≤ 4).

Output

For each dataset, write on one line the maximum point score a player could get.

ExamplesInput
1
10
G3B7B3Y6
R9B2B0G3
G0Y2Y1R7
G2B2B7G9
G2B9Y3G1
R9B1R4Y8
G5G3Y1R6
G2R6R5B4
R6R6R3B4
R2B4Y4G3
Output
517

加入题单

上一题 下一题 算法标签: