ZNO
ZNO (xarici müstəqil qiymətləndirmə) üçün nəzərdə tutulmuş auditoriya N sıra və hər sırada M partadan ibarətdir. Hər partada maksimum bir şagird otura bilər və yerlər püşkatma ilə təyin edilir. Lakin, eyni məktəbdən olan şagirdlərin yan-yana oturması mümkündür. ZNO-nun keçirilməsinə cavabdeh olan şəxs, şagirdlərin partalarda yerləşdirilməsinin "keyfiyyətini" ölçməyə qərar verir.
Partaların düzbucaqlı koordinatlarını belə təsvir edək: (sıra, yer). (x, y) və (x', y') koordinatları olan partalardakı şagirdlər arasındakı məsafəni d = |x - x'| + |y - y'| kimi təyin edək. Sinifdə oturma keyfiyyətini, eyni məktəbdən olan iki şagird arasındakı ən kiçik məsafə kimi müəyyən edək.
Əgər bütün şagirdlərin yerləşmə koordinatları və məktəb nömrələri verilmişsə, sinifdə şagirdlərin oturma keyfiyyətini tapın.
Giriş verilənləri
Girişin ilk sətiri sinifdəki sıra sayını və hər sıradakı parta sayını göstərən iki təbii ədəd N və M ehtiva edir.
Sonrakı N sətir hər biri M tam ədəd ehtiva edir və şagirdlərin yerləşməsini göstərir: j-ci ədəd (i+1)-ci sıranın sıfırdırsa, (i, j) koordinatlı parta boşdur, əks halda, həmin partada oturan şagirdin məktəb nömrəsidir. Məktəb nömrələri 1 ilə 2^31-1 arasında olan təbii ədədlərdir.
Giriş faylı ən azı iki eyni məktəb nömrəsi ehtiva edir.
Bütün testlərdə NM ≤ 2∙10^5. 30% testlərdə NM ≤ 10^3.
Çıxış verilənləri
Çıxışın yeganə sətiri sinifdə oturma keyfiyyətini göstərən bir təbii ədəd olmalıdır.