Size satır ve sütundan oluşan bir ızgara veriliyor. Satırlar yukarıdan aşağıya 'den 'ye, sütunlar ise soldan sağa 'den 'ye kadar numaralandırılmıştır. satırında ve sütununda bulunan her hücresinin bir rengi (mavi veya sarı) ve bir a_{i,j} ağırlığı vardır.
Bir -şekli, c_2 - c_1 \ge 2, k \ge 2, 1 \le c_1 < c_2 \le m ve 1 \le r, r + k - 1 \le n koşullarını sağlayan dört tam sayı , c_1, c_2 ve ile tanımlanır. Bu şekil, aşağıda bu sırayla listelenen hücrelerden oluşur:
Yani şekil, c_1 sütunu boyunca r + k - 1 satırından satırına kadar yukarı çıkar, sonra satırı boyunca c_1 sütunundan c_2 sütununa kadar sağa gider, ardından c_2 sütunu boyunca r + k - 1 satırına kadar aşağı iner. Şekil döndürülemez veya yansıtılamaz.
Yukarıdaki listede ardışık herhangi iki hücrenin renkleri farklıysa, -şekline iyi denir. Bir -şeklinin ağırlığı, onun 2k + c_2 - c_1 - 1 hücresinin tümü üzerinden a_{i,j} değerlerinin toplamıdır.
Izgaradaki iyi bir -şeklinin en büyük ağırlığını bulun veya böyle bir şeklin olmadığını bildirin.
İlk satırda bir tam sayı (1 \le t \le 2 \cdot 10^5) — test durumlarının sayısı verilir.
Her test durumunun ilk satırında iki tam sayı ve (1 \le n, m; n \cdot m \le 2 \cdot 10^5) — ızgaranın boyutları verilir.
Sonraki satırın her biri, ızgaranın bir satırını soldan sağa betimleyen karakterlik bir dizgi içerir. B karakteri mavi hücreyi, Y ise sarı hücreyi gösterir.
Sonraki satırın her biri tam sayı a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — satırındaki hücrelerin ağırlıklarını içerir.
Tüm test durumları üzerinden n \cdot m toplamı 2 \cdot 10^5 değerini aşmaz.
Her test durumu için bir tam sayı yazdırın: iyi bir -şeklinin en büyük ağırlığını, iyi bir -şekli yoksa .
Örnek 1
Birinci test durumunda en iyi -şeklinde r = 2, c_1 = 1, c_2 = 4 ve k = 3'tür. Bu şekil (4, 1), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4) hücrelerinden oluşur; renkleri sarı, mavi, sarı, mavi, sarı, mavi, sarı, mavi olduğundan şekil iyidir. Ağırlığı 9 + 2 + 2 + 9 + 9 + 9 + 1 + 1 = 42'dir.
İkinci test durumunda tek iyi -şekli, dışındaki tüm hücrelerden oluşur ve ağırlığı 1 + 2 + 3 + 4 + 6 = 16'dır.
Üçüncü test durumunda tek iyi -şeklinde r = 1, c_1 = 2, c_2 = 4 ve k = 2'dir.
Dördüncü test durumunda ızgaranın tek bir satırı vardır, bu yüzden k \ge 2 olması imkânsızdır ve hiç -şekli yoktur.