Dynamic Substring Programming


Plus
Pin


Problem description Progress
ID 38134. Balanced Subsets
Темы: Dynamic Substring Programming    Suffix array   

Farmer John's pasture can be represented as a huge 2D grid of cells labeled with ordered pairs (i,j) for all 1≤i≤N, 1≤j≤N (1≤N≤150). Some of these slots contain grass.
A non-empty subset of lattice cells is called "balanced" if the following conditions are met:

All subset cells contain grass.
The subset is 4-connected. In other words, there is a path from any cell in the subset to any other cell in the subset such that two consecutive cells of the path are horizontally or vertically adjacent.
If cells (x1,y) (x2,y) (x1≤x2) is part of the subset, then all cells (x,y) with x1≤x≤x2 are also part of the subset.
If cells (x,y1) and (x,y2) (y1≤y2 ) is part of the subset, then all cells (x,y) with y1≤y≤y2 are also part of the subset.
Count the number of balanced subsets modulo 109+7.

Input: 
The first line contains the number N.
Each of the subsequent N lines contains a string of N characters. The j-th character of string i from the top is equal to G if cell (i,j) contains grass or character . otherwise.

Output: 
Number of balanced subsets modulo 109+7.
 

Examples
# Input Output Explanation
1 2
GG
GG
13 For this test, all 4-connected subsets are balanced.

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2 4
GGGG
GGGG
GG.G
GGGG
  642
Below is an example of a subset that satisfies the second condition (4-connectedness) but does not satisfy the third condition:

GG..
.G..
GG..
....

ID 38570. Casino
Темы: Dynamic Substring Programming   

The newly opened casino offered an original game.

At the beginning of the game, the croupier places several chips of different colors in a row. In addition, he announces which sequences of chips the player can take during the game. Next, the player takes one of the pre-announced sequences of chips arranged in a row. After that, the croupier moves the remaining chips, removing the gap. Then the player again takes one of the declared sequences for himself, and so on. The game continues as long as the player can collect chips.

Consider an example. Let there be a row of rrrgggbbb chips on the table, and the croupier announces the sequences rg and gb. The player, for example, can pick up the rg chips lying in the third and fourth places from the left. After that, the croupier will move the chips, and a row of rrggbbb will appear on the table. Taking the rg chips twice more, the player will ensure that the bbb chips remain on the table and the game will end, since the player has nothing more to take from the table. The player could have acted differently — on the second and third moves, take not sequences rg, but sequences gb. Then there would be rrb chips on the table. Likewise, the player could have the rrr or rbb rows at the end.

After the end of the game, the player exchanges the received chips for money. The price of a chip depends on its color.

It is required to write a program that determines the maximum amount that a player can receive.

Input
The first line of the input contains the number K (1 ≤ K ≤ 26) — the number of chip colors. Each of the next K lines starts with a lowercase latin letter denoting a color. Further on the same line, space-separated integer Xi (1 ≤ Xi ≤ 150, i = 1..K) — the price of the corresponding color chip.

The (K+2)-th line describes a row of chips lying on the table at the beginning of the game. The row is given by L lowercase Latin letters (1 ≤ L ≤ 150), which indicate the colors of the chips in the row.

The next line contains the number N(1 ≤ N ≤ 150) — the number of sequences that were announced by the croupier. The next N lines contain these sequences. It is guaranteed that the sum of the lengths of these N strings does not exceed 150 characters, and they are all non-empty.

Imprint
Print a single integer — the maximum amount of money a player can receive.
 

Examples
# Input Output
1 3
v3
l 1
u 2
luvu
3

vul
uuu
6