405591: GYM102006 D Carnival Slots

You go to the carnival and come across a nice little game. The carnival worker shows you the setup of the game, which can be represented as a 2-dimensional grid g with r rows and c columns. You are given the opportunity to change around the grid and maximize your score before the worker drops several balls into each column.

A cell in the i^th row (from top) and the j^th column (from left) is denoted by (i, j), and can be one of three different types of cells:

1. '.'; a ball that enters this cell will go to cell (i + 1, j).
2. '\'; a ball that enters this cell will go to cell (i + 1, j + 1).
3. '/'; a ball that enters this cell will go to cell (i + 1, j - 1).

You may change a cell of type 2 and 3 to any of the three types, and you can change as many cells as you want. Cells of type 1 can't be changed.

Under the grid is aligned c buckets, where the i^th bucket is below the i^th column.

Each of the c buckets contains a score. For every ball that falls into a bucket, the score on that bucket is added to your total score and that ball stops. A ball that doesn't fall into a bucket gets a score of 0.

You are given how many balls the worker will drop into each column. Balls are dropped one after the another such that no two balls will collide. After making the changes, what is the maximum score you can achieve?

Your only condition for the grid g is that it's not allowed to have two adjacent cells in one row such that the left one is '\' and the right one is '/'.

The first line of input contains a single integer T (1 ≤ T ≤ 5300), the number of test cases.

The first line of each test case contains two space-separated integers r and c (1 ≤ r, c ≤ 500), the dimensions of the grid.

The following line contains c space-separated integers b₁, b₂, ..., b_c (0 ≤ b_i ≤ 10⁸), where b_i is the number of balls dropped into the i^th column.

Each of the following r lines contains c characters, representing the grid. Each character is either '.', '\', or '/'.

The last line of each test case contains c space-separated integers s₁, s₂, ..., s_c (0 ≤ s_i ≤ 10⁸), where s_i is the score added after one ball drops into the i^th bucket.

The sum of r × c over all test cases doesn't exceed 4 × 10⁶.

For each test case, print on a single line the maximum score possible.

2
3 3
1 2 1
../
./.
\..
10 5 20
1 2
100000000 100000000
..
1 100000000

70
10000000100000000