Mozaika tağı#13114

Mozaika tağı

1 saniyə
256 meqabayt

Sizə sətir və sütundan ibarət cədvəl verilmişdir. Sətirlər yuxarıdan aşağıya -dən -ə qədər, sütunlar isə soldan sağa -dən -ə qədər nömrələnmişdir. sətrində və sütununda yerləşən hər bir xanasının rəngi (mavi və ya sarı) və a_{i,j} çəkisi var.

-fiqur c_2 - c_1 \ge 2, k \ge 2, 1 \le c_1 < c_2 \le m və 1 \le r, r + k - 1 \le n şərtlərini ödəyən dörd tam ədədlə — , c_1, c_2 və — təyin olunur. O, aşağıdakı ardıcıllıqla sadalanan xanalardan ibarətdir:

(r + k - 1, c_1), \ldots, (r + 1, c_1), (r, c_1), (r, c_1 + 1), \ldots, (r, c_2), (r + 1, c_2), \ldots, (r + k - 1, c_2).

Yəni fiqur c_1 sütunu boyunca r + k - 1 sətrindən sətrinə qədər yuxarı qalxır, sonra sətri boyunca c_1 sütunundan c_2 sütununa qədər sağa gedir, daha sonra isə c_2 sütunu boyunca r + k - 1 sətrinə qədər aşağı enir. Fiquru döndərmək və ya əks etdirmək olmaz.

Əgər yuxarıdakı siyahıda istənilən iki qonşu xananın rəngləri fərqlidirsə, -fiqur yaxşı adlanır. -fiqurun çəkisi onun bütün 2k + c_2 - c_1 - 1 xanası üzrə a_{i,j} qiymətlərinin cəmidir.

Cədvəldə yaxşı -fiqurun ən böyük çəkisini tapın və ya belə fiqurun mövcud olmadığını bildirin.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 2 \cdot 10^5) — testlərin sayı verilir.

Hər testin birinci sətrində iki tam ədəd və (1 \le n, m; n \cdot m \le 2 \cdot 10^5) — cədvəlin ölçüləri verilir.

Sonrakı sətrin hər biri cədvəlin bir sətrini soldan sağa təsvir edən simvoldan ibarətdir. B simvolu mavi xananı, Y isə sarı xananı bildirir.

Sonrakı sətrin hər birində tam ədəd a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^9) — sətrindəki xanaların çəkiləri verilir.

Bütün testlər üzrə n \cdot m cəmi 2 \cdot 10^5-i aşmır.

Çıxış

Hər test üçün bir tam ədəd çap edin: yaxşı -fiqurun ən böyük çəkisini, yaxşı -fiqur yoxdursa isə .

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci testdə ən yaxşı -fiqur üçün r = 2, c_1 = 1, c_2 = 4 və k = 3. O, (4, 1), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4) xanalarından ibarətdir, onların rəngləri sarı, mavi, sarı, mavi, sarı, mavi, sarı, mavidir, deməli fiqur yaxşıdır. Onun çəkisi 9 + 2 + 2 + 9 + 9 + 9 + 1 + 1 = 42-dir.

İkinci testdə yeganə yaxşı -fiqur xanasından başqa bütün xanalardan ibarətdir və onun çəkisi 1 + 2 + 3 + 4 + 6 = 16-dır.

Üçüncü testdə yeganə yaxşı -fiqur üçün r = 1, c_1 = 2, c_2 = 4 və k = 2.

Dördüncü testdə cədvəlin yalnız bir sətri var, buna görə də k \ge 2 mümkün deyil və ümumiyyətlə heç bir -fiqur yoxdur.