MAXCOMP

Bir matris üçün hüceyrələrin bir alt qüməsini S adlandıraq. Əgər S-dəki hər hansı iki hüceyrə arasında yalnız S-dən olan hüceyrələrdən ibarət bir yol varsa, bu alt qümə əlaqəli sayılır. Yol, u[1], u[2], ..., u[k] ardıcıllığıdır, burada u[i] və u[i+1] hər hansı i=1,k-1 üçün qonşudur.

N sətir və M sütundan ibarət A matrisinə verilmişdir. A-nın əlaqəli alt qüməsi S üçün aşağıdakı formulu müəyyən edirik:çəkisi(S) = (max{A(s)|s∈S} - min{A(s)|s∈S} - |S|).burada |*| bir qümənin kardinalını təmsil edir və A(s) A-da s hüceyrəsinin dəyərini təmsil edir.

Giriş

Girişin ilk sətri matris A-nın ölçülərini təmsil edən iki ədəd N və M ehtiva edir.

N növbəti sətir matrisi təsvir edir. i-ci sətir M ədəd ehtiva edir, burada j-ci dəyər A(i,j)-ni təmsil edir.

Çıxış

Verilmiş matrisin bütün əlaqəli komponentləri S arasında çəkisi(S)-in maksimum dəyərini çap edin.

Ümumi məhdudiyyətlər

0 ≤ A(i,j) ≤ 10^91 ≤ N , M ≤ 10^3

Alt tapşırıqlar

• 15 xal üçün: 1 ≤ N*M ≤ 20

• Digər 15 xal üçün: N = 1

• Digər 30 xal üçün: N,M ≤ 20

İzah

Optimal əlaqəli alt qümələrdən biri {(1,1),(1,2),(2,2)}-dir. {(1,1),(2,2)} həll deyil, çünki (1,1) və (2,2) arasında yol yoxdur.