Гильдон приобрел известный графический редактор cfpaint. Рабочая зона cfpaint — квадрат, состоящий из \(n\) строк и \(n\) столбцов квадратных клеток. Строки пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы — от \(1\) до \(n\) слева направо. Будем обозначать клетку в строке \(r\) и столбце \(c\) как \((r, c)\). Каждая клетка может иметь один из двух цветов — белый или черный.
В cfpaint есть инструмент, называемый ластиком. Ластик имеет размер \(k\) (\(1 \le k \le n\)). Чтобы его использовать, Гильдон должен щелкнуть в некоторую клетку \((i, j)\), где \(1 \le i, j \le n - k + 1\). Если он щелкнет в клетку \((i, j)\), то все клетки \((i', j')\) такие, что \(i \le i' \le i + k - 1\) и \(j \le j' \le j + k - 1\) станут белыми. Иными словами, квадрат со стороной в \(k\) клеток, левый верхний угол которого находится в клетке \((i, j)\), будет закрашен белым.
Белой полосой называется строка или столбец, не содержащие черных клеток.
Гильдон уже некоторое время использовал cfpaint, поэтоому некоторый клетки (возможно, все или ни одной) сейчас черные. Он хочет узнать максимальное число белых полос после того, как он использует ластик ровно один раз. Помогите Гильдону найти ответ на его вопрос.
Примечание
В первом примере Гильдон может щелкнуть в клетку \((2, 2)\), тогда рабочая зона будет выглядеть так:
BWWW
WWWW
WWWW
WWWB
Здесь есть четыре белых полосы: \(2\)-я и \(3\)-я строки, а также \(2\)-й и \(3\)-й столбцы.
Во втором примере нажатие на клетку \((2, 3)\) сделает \(2\)-ю строку белой.
В третьем примере \(2\)-й столбец и \(5\)-я строка станут белыми полосами, если щелкнуть в клетку \((3, 2)\).