MAXCOMP — Eolymp

Вхідні дані

Перший рядок вхідних даних містить два числа $N$ та $M$ , що представляють розміри матриці $A$ .

Наступні $N$ рядків описують матрицю. $i$ -й рядок містить $M$ цілих чисел, де $j$ -те значення представляє $A (i, j)$ A(i,j).

Обмеження: $0 \leq A (i, j) \leq 1 0^{9}$ 0 \le A(i,j) \le 10^9, $1 \leq N, M \leq 1 0^{3}$ 1 \le N, M \le 10^3.

Вихідні дані

Виведіть максимальне значення $вага (S)$ серед усіх зв'язаних компонент $S$ даної матриці.

Приклади

Приклад 1

Loading

Примітка

Однією з оптимальних зв'язаних підмножин є ${(1, 1), (1, 2), (2, 2)}$ \{(1,1),(1,2),(2,2)\}. ${(1, 1), (2, 2)}$ \{(1,1),(2,2)\} не є рішенням, оскільки немає шляху між $(1, 1)$ та $(2, 2)$ .

Оцінювання

За 15 балів: $1 \leq N \cdot M \leq 20$ 1 \le N \cdot M \le 20
За інші 15 балів: $N = 1$ N = 1
За інші 30 балів: $N, M \leq 20$ N, M \le 20