Задано таблицю з рядків і стовпців. Рядки пронумеровано від до згори донизу, а стовпці — від до зліва направо. Кожна клітинка , що стоїть у рядку та стовпці , має колір (синій або жовтий) і вагу a_{i,j}.
-фігура задається чотирма цілими числами , c_1, c_2 і такими, що c_2 - c_1 \ge 2, k \ge 2, 1 \le c_1 < c_2 \le m і 1 \le r, r + k - 1 \le n. Вона складається з клітинок, перелічених у такому порядку:
Тобто фігура йде вгору стовпцем c_1 від рядка r + k - 1 до рядка , потім праворуч рядком від стовпця c_1 до стовпця c_2, а потім униз стовпцем c_2 до рядка r + k - 1. Фігуру не можна повертати чи відображати.
-фігура називається гарною, якщо будь-які дві сусідні клітинки в наведеному вище переліку мають різні кольори. Вага -фігури — це сума a_{i,j} за всіма її 2k + c_2 - c_1 - 1 клітинками.
Знайдіть найбільшу вагу гарної -фігури в таблиці або повідомте, що такої немає.
Перший рядок містить одне ціле число (1 \le t \le 2 \cdot 10^5) — кількість тестових випадків.
Перший рядок кожного тестового випадку містить два цілі числа і (1 \le n, m; n \cdot m \le 2 \cdot 10^5) — розміри таблиці.
Кожен з наступних рядків містить рядок з символів, що описує рядок таблиці зліва направо. Символ B позначає синю клітинку, а Y — жовту.
Кожен з наступних рядків містить цілих чисел a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — ваги клітинок рядка .
Сума n \cdot m за всіма тестовими випадками не перевищує 2 \cdot 10^5.
Для кожного тестового випадку виведіть одне ціле число: найбільшу вагу гарної -фігури або , якщо гарної -фігури немає.
Приклад 1
У першому тестовому випадку найкраща -фігура має r = 2, c_1 = 1, c_2 = 4 і k = 3. Вона складається з клітинок (4, 1), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), кольори яких — жовтий, синій, жовтий, синій, жовтий, синій, жовтий, синій, тож вона гарна. Її вага дорівнює 9 + 2 + 2 + 9 + 9 + 9 + 1 + 1 = 42.
У другому тестовому випадку єдина гарна -фігура складається з усіх клітинок, крім , і її вага дорівнює 1 + 2 + 3 + 4 + 6 = 16.
У третьому тестовому випадку єдина гарна -фігура має r = 1, c_1 = 2, c_2 = 4 і k = 2.
У четвертому тестовому випадку таблиця має лише один рядок, тому k \ge 2 неможливо і жодної -фігури немає.