Дана сетка \(a\) размера \(n \times m\) из неотрицательных целых чисел, где \(a_{i,j}\) представляет глубину воды в \(i\)-й строке и \(j\)-м столбце.
Озеро — это набор ячеек, таких что:
- Каждая ячейка в наборе имеет \(a_{i,j} > 0\)
- Существует путь между любой парой ячеек в озере, двигаясь вверх, вниз, влево или вправо, несколько раз и не наступая на ячейку с \(a_{i,j} = 0\).
Объем озера — это сумма глубин всех ячеек в озере.
Найдите наибольший объем озера в сетке.
Выходные данные
Для каждого теста выведите одно целое число — наибольший объем озера в сетке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 3
1 2 0
3 4 0
0 0 5
1 1
0
3 3
0 1 1
1 0 1
1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 0 5 0 1
1 0 0 0 1
1 1 1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 1 4 0 1
1 0 0 0 1
1 1 1 1 1
|
10
0
7
16
21
|