You are given a grid with rows and columns. The rows are numbered from to from top to bottom, and the columns from to from left to right. Every cell , in row and column , has a colour (blue or yellow) and a weight a_{i,j}.
A -shape is defined by four integers , c_1, c_2 and such that c_2 - c_1 \ge 2, k \ge 2, 1 \le c_1 < c_2 \le m and 1 \le r, r + k - 1 \le n. It consists of the cells, listed in this order:
That is, the shape goes up along column c_1 from row r + k - 1 to row , then right along row from column c_1 to column c_2, and then down along column c_2 to row r + k - 1. The shape cannot be rotated or flipped.
A -shape is called good if any two consecutive cells in the list above have different colours. The weight of a -shape is the sum of a_{i,j} over all its 2k + c_2 - c_1 - 1 cells.
Find the largest weight of a good -shape in the grid, or report that there is none.
The first line contains a single integer (1 \le t \le 2 \cdot 10^5) — the number of test cases.
The first line of each test case contains two integers and (1 \le n, m; n \cdot m \le 2 \cdot 10^5) — the size of the grid.
Each of the next lines contains a string of characters describing a row of the grid from left to right. The character B stands for a blue cell, and Y for a yellow one.
Each of the next lines contains integers a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — the weights of the cells of row .
The sum of n \cdot m over all test cases does not exceed 2 \cdot 10^5.
For each test case print one integer: the largest weight of a good -shape, or if there is no good -shape.
Example 1
In the first test case the best -shape has r = 2, c_1 = 1, c_2 = 4 and k = 3. It consists of the cells (4, 1), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), whose colours are yellow, blue, yellow, blue, yellow, blue, yellow, blue, so it is good. Its weight is 9 + 2 + 2 + 9 + 9 + 9 + 1 + 1 = 42.
In the second test case the only good -shape consists of all cells except , and its weight is 1 + 2 + 3 + 4 + 6 = 16.
In the third test case the only good -shape has r = 1, c_1 = 2, c_2 = 4 and k = 2.
In the fourth test case the grid has a single row, so k \ge 2 is impossible and there is no -shape at all.