310411: CF1829E. The Lakes

E. The Lakestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an $n \times m$ grid $a$ of non-negative integers. The value $a_{i,j}$ represents the depth of water at the $i$-th row and $j$-th column.

A lake is a set of cells such that:

• each cell in the set has $a_{i,j} > 0$, and
• there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $a_{i,j} = 0$.

The volume of a lake is the sum of depths of all the cells in the lake.

Find the largest volume of a lake in the grid.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n, m$ ($1 \leq n, m \leq 1000$) — the number of rows and columns of the grid, respectively.

Then $n$ lines follow each with $m$ integers $a_{i,j}$ ($0 \leq a_{i,j} \leq 1000$) — the depth of the water at each cell.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the largest volume of a lake in the grid.

ExampleInput

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

Output

10
0
7
16
21

题目大意：给定一个非负整数矩阵 $ a $，其中每个元素 $ a_{i,j} $ 代表网格中第 $ i $ 行第 $ j $ 列的水深。湖泊是由一组单元格组成的，这些单元格满足：集合中的每个单元格都有 $ a_{i,j} > 0 $，并且湖泊中的任意两个单元格之间都存在一条路径，可以通过上、下、左、右移动而不会踩到 $ a_{i,j} = 0 $ 的单元格。湖泊的体积是湖泊中所有单元格深度的总和。需要在网格中找到最大湖泊的体积。

输入数据格式：第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。每个测试用例的第一行包含两个整数 $ n, m $（$ 1 \leq n, m \leq 1000 $），分别代表网格的行数和列数。接下来 $ n $ 行，每行包含 $ m $ 个整数 $ a_{i,j} $（$ 0 \leq a_{i,j} \leq 1000 $），代表每个单元格的水深。所有测试用例的 $ n \cdot m $ 之和不超过 $ 10^6 $。

输出数据格式：对于每个测试用例，输出一个整数，表示网格中最大湖泊的体积。

例：

输入：
```
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
```题目大意：给定一个非负整数矩阵 $ a $，其中每个元素 $ a_{i,j} $ 代表网格中第 $ i $ 行第 $ j $ 列的水深。湖泊是由一组单元格组成的，这些单元格满足：集合中的每个单元格都有 $ a_{i,j} > 0 $，并且湖泊中的任意两个单元格之间都存在一条路径，可以通过上、下、左、右移动而不会踩到 $ a_{i,j} = 0 $ 的单元格。湖泊的体积是湖泊中所有单元格深度的总和。需要在网格中找到最大湖泊的体积。 输入数据格式：第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。每个测试用例的第一行包含两个整数 $ n, m $（$ 1 \leq n, m \leq 1000 $），分别代表网格的行数和列数。接下来 $ n $ 行，每行包含 $ m $ 个整数 $ a_{i,j} $（$ 0 \leq a_{i,j} \leq 1000 $），代表每个单元格的水深。所有测试用例的 $ n \cdot m $ 之和不超过 $ 10^6 $。 输出数据格式：对于每个测试用例，输出一个整数，表示网格中最大湖泊的体积。 例： 输入： ``` 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 ```