Paylanmış

Fermer Con otlayan inəklərinin şəklini çəkib divara asmaq istəyir. Otlaq n * n ölçülü bir şəbəkə ilə təsvir olunur (şahmat taxtası ölçüsündə n * n). Con inəkləri otlaqda aşağıdakı qaydalara uyğun yerləşdirmək istəyir:

• Heç bir iki inək eyni hüceyrədə ola bilməz.

• Hər bir 2 * 2 ölçülü altşəbəkə (cəmi belə altşəbəkələr (n − 1) * (n − 1)) dəqiq 2 inək içərməlidir.

Məsələn, bu yerləşdirmə qaydalara uyğundur:

CCC
...
CCC

Amma bu yerləşdirmə uyğun deyil:

C.C
.C.
C..

çünki sağ alt küncdəki 2 * 2 bölgə yalnız bir inək ehtiva edir.

Başqa məhdudiyyətlər yoxdur. Siz Conun sonsuz sayda inəyi olduğunu qəbul edə bilərsiniz.

Bəzi hüceyrələr Con üçün daha üstünlük təşkil edir. Xüsusilə, Con hesab edir ki, əgər inək (i, j) hüceyrəsində yerləşdirilərsə, şəkilin gözəlliyi a[ij] (0 ≤ a[ij] ≤ 1000) vahid artır.

Düzgün inək yerləşdirməsinin mümkün olan maksimum gözəlliyini müəyyən edin.

Giriş məlumatları

Birinci sətir n (2 ≤ n ≤ 1000) ədədini ehtiva edir. Sonrakı n sətirin hər biri n tam ədəd ehtiva edir. i-ci sətirdəki j-ci ədəd a[ij] dəyəridir.

Çıxış məlumatları

Bir tam ədəd çıxarın - nəticə şəkilinin mümkün olan maksimum gözəlliyi.

Nümunə

Bu nümunədə maksimum gözəllik aşağıdakı yerləşdirmə ilə əldə edilə bilər:

CC..
..CC
CC..
..CC

Bu yerləşdirmənin gözəlliyi 3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22.