D. Milad Ekspresi

Rojdestvo Ekspressi — şimal qütbünün dairəvi metrosu ilə hər kəsi daşıya bilən qatar. Dairəvi metro $1$-dən $n$-ə qədər tam ədədlərlə nömrələnmiş $n$ stansiyadan ibarətdir. Ekspress $1,2,\dots ,n,1,2,\dots ,n,1,2,\dots$ nömrəli stansiyalarda dayanacaq və bu ardıcıllıqla davam edəcək...

Son iki ilin statistikasına əsasən, Şaxta Baba müəyyən edib ki, qatar hər dəfə $i$ nömrəli stansiyada dayandıqda, hər bir $j$ ($j\ne i$) üçün $1$-dən $n$-ə qədər $a_{i,j}$ elf qatara minəcək və $j$ nömrəli stansiyada düşəcək. Şaxta Babanın vacib bir sualı var — qütb sakinlərinin ehtiyaclarını ödəmək üçün qatarda ola biləcək minimal oturacaq sayı nə qədərdir?

Siz qəbul edə bilərsiniz ki, hər hansı bir stansiyada dayanarkən sərnişinlər əvvəlcə qatardan düşür, sonra isə digər sərnişinlər qatara minir. Əlbəttə, Şaxta Babaya kömək etmək sizə düşür.

Giriş verilənləri

Birinci sətir bir tam ədəd $n$ ($2\le n\le 500$) ehtiva edir.

Sonrakı $n$ sətirin hər biri $n$ tam ədəd $a_{i,1},a_{i,2},\dots ,a_{i,n}$ ($0\le a_{i,j}\le 500$) ehtiva edir. Bütün $a_{i,i}$ dəyərləri $0$-a bərabərdir.

Çıxış verilənləri

Bir tam ədəd çıxarın — məsələnin cavabı.

Nümunələr

Qeyd

Əgər qatar eyni anda yalnız səkkiz sərnişin daşıya bilsə, bütün elfler ona sığmayacaq; qatarda doqquz yer kifayətdir ki, elfler üçün kifayət qədər yer olsun.