{"extraResources":{"example.01.mu":"TVXzATUNCiFjMTsyIDINCi4uDQouLg0KIWMyOzQgNQ0KIyMjLiMNCiMuLi4uDQouIyMuIw0KIy4jLiMNCiFjMzsyIDENCi4NCi4NCiFjNDsyIDMNCiMjIw0KIy4jDQohYzU7NSA0DQojIy4jDQouLiMuDQojLiMuDQouLi4uDQojLiMjDQo="},"scoring":null,"notes":"","legend":"Bob is decorating a loft-style rectangular wall with bricks. The wall consists of $n \\times m$ unit cells. Some cells are already occupied by bricks, while the remaining cells are empty.\r\n\r\nBob wants to add up to two more bricks to this wall. New bricks must have a width equal to $1$ unit and can have any positive integer length. Each brick can only be placed horizontally or vertically, so each new brick will occupy several consecutive empty cells in one row or in one column. Also, these two bricks must not intersect, i.e. occupy the same cell.\r\n\r\nWhat is the maximum possible sum of lengths of at most two new bricks that Bob can add to this wall?","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"For each test case, print a single integer~--- the maximum possible sum of lengths of at most two new bricks.","inputFile":"stdin","outputFile":"stdout","input":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \\le t \\le 10^4$). The description of the test cases follows.\r\n\r\nThe first line of each test case contains two integers $n$ and $m$~--- the height and the width of the wall ($1 \\le n, m$; $n \\cdot m \\le 10^6$).\r\n\r\nThe next $n$ lines contain $m$ characters each, describing the wall. An occupied cell is denoted by `\\t{\\#}', an empty cell is denoted by `\\t{.}'.\r\n\r\nIt is guaranteed that the sum of $n \\cdot m$ over all test cases does not exceed $10^6$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"4\r\n6\r\n2\r\n1\r\n7\r\n","input":"5\r\n2 2\r\n..\r\n..\r\n4 5\r\n###.#\r\n#....\r\n.##.#\r\n#.#.#\r\n2 1\r\n.\r\n.\r\n2 3\r\n###\r\n#.#\r\n5 4\r\n##.#\r\n..#.\r\n#.#.\r\n....\r\n#.##\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Bricks in the Wall","interaction":null,"memoryLimit":536870912,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Виталий Аксенов\\\\\r\n         Разработка: & Николай Будин\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nВам дана таблица, заполненная нулями и единицами. Вам нужно найти две непересекающихся полоски (прямоугольника с высотой или шириной равной $1$) из нулей, с максимальной возможной суммарной длиной.\r\n\r\nВычислим значения $d_u[x][y]$, $d_d[x][y]$, $d_l[x][y]$, $d_r[x][y]$ для каждой клетки $(x, y)$~--- длину наибольшей полоски из нулей, начинающейся в клетке $(x, y)$ в направлении вверх/вниз/влево/вправо, соответственно. Эти значения можно вычисить за время $O(n \\cdot m)$. Например, можно выделить все максимальные по включению горизонтальные и вертикальные полоски за длину каждой из таких полосок. Либо можно воспользоваться динамическим программированием.\r\n\r\nЛюбые два непересекающихся прямоугольника (с вертикальными и горизонтальными сторонами) можно разделить какой-то вертикальной или горизонтальной прямой. Переберем эту прямую, разделяющую два прямоугольника. Не умаляя общности, пусть мы выбрали горизонтальную прямую. Тогда нужно найти максимальную полоску сверху от этой прямой, и максимальную полоску снизу от этой прямой. Чтобы найти максимальную полоску сверху, нужно взять максимум по всем $d_u[x][y]$ и $d_r[x][y]$ для всех клеток сверху от прямой. Чтобы не перебирать все такие клетки для каждой прямой, будем двигать прямую сверху вниз, при этом множество клеток будет расширяться, и нам нужно будет в максимум добавлять новые значения. Аналогично для полоски снизу от прямой.\r\n\r\nИ аналогично для вертикальных прямых. Чтобы уменьшить число случаев, можно сначала решить задачу с горизонтальной прямой для исходной таблицы, а потом повернуть таблицу на 90 градусов и ещё раз запустить то же решение.\r\n\r\n%You are given a grid of zeroes and ones. And you want to find two non-intersecting stripes (rectangles with a width or a height equal to 1) of zeroes with the maximum possible total length.\r\n\r\n%Let's calculate four values $d_u[x][y]$, $d_d[x][y]$, $d_l[x][y]$, $d_r[x][y]$ for every cell $(x, y)$~--- length of the longest stripe starting in the cell $(x, y)$ and going upward/downward/to the left/to the right respectively. These values can be calculated in $O(n \\cdot m)$ time.\r\n\r\n%Any two non-intersecting rectangles can be divided by some vertical or horizontal line. Let's iterate over all such lines. Without loss of generality, we've chosen a horizontal line. Now we want to find the longest stripe above it and below it. In order to find the length of the longest stripe above the line, you can calculate the maximum over all $d_u[x][y]$ and $d_r[x][y]$ for all cells above the line. And similarly for the part below the line."}