Se te da una cuadrícula con filas y columnas. Las filas están numeradas de a de arriba abajo, y las columnas de a de izquierda a derecha. Cada celda , situada en la fila y la columna , tiene un color (azul o amarillo) y un peso a_{i,j}.
Una figura en se define mediante cuatro enteros , c_1, c_2 y tales que c_2 - c_1 \ge 2, k \ge 2, 1 \le c_1 < c_2 \le m y 1 \le r, r + k - 1 \le n. Está formada por las celdas, enumeradas en este orden:
Es decir, la figura sube por la columna c_1 desde la fila r + k - 1 hasta la fila , luego avanza hacia la derecha por la fila desde la columna c_1 hasta la columna c_2, y después baja por la columna c_2 hasta la fila r + k - 1. La figura no se puede rotar ni reflejar.
Una figura en se llama buena si dos celdas consecutivas cualesquiera de la lista anterior tienen colores distintos. El peso de una figura en es la suma de a_{i,j} sobre todas sus 2k + c_2 - c_1 - 1 celdas.
Halla el mayor peso de una figura en buena en la cuadrícula, o informa de que no existe ninguna.
La primera línea contiene un único entero (1 \le t \le 2 \cdot 10^5) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, m; n \cdot m \le 2 \cdot 10^5) — el tamaño de la cuadrícula.
Cada una de las siguientes líneas contiene una cadena de caracteres que describe una fila de la cuadrícula de izquierda a derecha. El carácter B representa una celda azul, y Y, una amarilla.
Cada una de las siguientes líneas contiene enteros a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — los pesos de las celdas de la fila .
La suma de n \cdot m sobre todos los casos de prueba no supera 2 \cdot 10^5.
Para cada caso de prueba imprime un entero: el mayor peso de una figura en buena, o si no existe ninguna figura en buena.
Ejemplo 1
En el primer caso de prueba la mejor figura en tiene r = 2, c_1 = 1, c_2 = 4 y k = 3. Está formada por las celdas (4, 1), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), cuyos colores son amarillo, azul, amarillo, azul, amarillo, azul, amarillo, azul, así que es buena. Su peso es 9 + 2 + 2 + 9 + 9 + 9 + 1 + 1 = 42.
En el segundo caso de prueba la única figura en buena está formada por todas las celdas excepto , y su peso es 1 + 2 + 3 + 4 + 6 = 16.
En el tercer caso de prueba la única figura en buena tiene r = 1, c_1 = 2, c_2 = 4 y k = 2.
En el cuarto caso de prueba la cuadrícula tiene una sola fila, por lo que k \ge 2 es imposible y no existe ninguna figura en en absoluto.