Zirvələr
Bir dağlıq adada yaşayan bir alpinist, artıq bir zirvəyə dırmaşıb və indi daha yüksək bir zirvəyə çatmaq istəyir.
Dəqiq desək, adanın hər nöqtəsi dəniz səviyyəsindən yuxarıdadır (dəniz səviyyəsi 0-dır) və əgər alpinist hazırda E_i yüksəklik səviyyəsindədirsə, onun məqsədi E_j yüksəklik səviyyəsinə malik bir zirvəyə çatmaqdır (E_j > E_i). Çünki o, bir zirvədədir, dərhal yuxarıya doğru bir yol yoxdur – daha yüksək bir nöqtəyə çatmaq üçün alpinist əvvəlcə aşağıya, daha aşağı bir səviyyəyə enməli və yalnız sonra yenidən yuxarıya qalxa bilər. Aşağıya eniş heç vaxt yuxarıya qalxış qədər diqqətəlayiq deyil, buna görə də alpinist, cari yerdən daha yüksək zirvəyə gedən yolda ən aşağı nöqtənin yüksəklik səviyyəsini maksimum etmək istəyir.
Məsələn, adanın profili şəkildə göstərildiyi kimi olarsa və alpinist E_4 yüksəklik səviyyəsindədirsə, daha yüksək üç zirvə var (E_5, E_6 və E_7), lakin ən aşağı nöqtənin ən yüksək yüksəklik səviyyəsinə malik olduğu yol E_7 yüksəklik səviyyəsinə malik zirvəyə gedən yoldur – bu yolda o, heç vaxt E_2 səviyyəsindən aşağıya enmir (digər hallarda o, E_1 səviyyəsinə enməyə məcbur olacaq). Əgər o, E_5-dən başlasaydı, müvafiq ən aşağı səviyyə E_3 olardı (E_6-ya gedən yol), lakin əgər o, E_6-dan başlasaydı, bu E_1 olardı.
Adanın xəritəsi iki ölçülü düzbucaqlı bir cədvəl şəklindədir və adanın müəyyən hissələrinin yüksəklik səviyyəsini təsvir edir – hüceyrədəki rəqəm adanın müvafiq bölgəsinin yüksəklik səviyyəsini göstərir. İki hüceyrə, ortaq bir nöqtəni paylaşırsa, qonşu sayılır. Beləliklə, hər bir hüceyrə (sərhəddə olanlar istisna olmaqla) səkkiz digər hüceyrə ilə qonşudur. Bir yol, hər iki ardıcıl hüceyrənin qonşu olduğu hüceyrələr ardıcıllığıdır. Düz bir sahə, eyni yüksəklik səviyyəsinə malik olan bir və ya daha çox hüceyrədən ibarət bir dəstdir, onların hər hansı bir cütü yalnız dəst daxilindəki hüceyrələri ziyarət edən bir yol ilə birləşdirilir. Eyni yüksəklik səviyyəsinə malik olan iki qonşu hüceyrə eyni düz sahəyə aiddir. Zirvə, hüceyrələrinin daha yüksək yüksəklik səviyyəsinə malik olan heç bir qonşu hüceyrəsi olmayan düz bir sahədir.
Adadakı bütün zirvələri tapan və hər biri üçün daha yüksək bir zirvəyə gedən yolda mümkün olan ən yüksək ən aşağı nöqtənin yüksəklik səviyyəsini tapan bir proqram yazın. Adadakı ən yüksək zirvə üçün (bu adada daha yüksək zirvə olmadığı üçün) alpinistin daha yüksək zirvələr axtararaq adanı tərk edəcəyini qəbul edirik, beləliklə, ən aşağı nöqtə 0 (dəniz səviyyəsi) olacaq.
Giriş verilənləri
Giriş faylının ilk sətrində xəritənin hündürlüyü və eni olan iki müsbət tam ədəd N və M (1 ≤ N, M ≤ 2000, N×M ≤ 10^5) verilir. Növbəti N sətir adanın xəritəsinin təsvirini ehtiva edir. Bu sətirlərin hər biri boşluqlarla ayrılmış M tam ədəd E_ij (1 ≤ E_ij ≤ 10^6) ehtiva edir. Hüceyrənin E_ij yüksəklik səviyyəsi (xəritədə i-ci sıra və j-ci sütuna uyğun gələn) faylın i+1-ci sətrində j-ci rəqəm kimi verilir.
Çıxış verilənləri
Çıxış faylının ilk sətri adada tapılan zirvələrin sayını göstərən bir tam ədəd P olmalıdır. Növbəti P sətir hər biri iki tam ədəd ehtiva etməlidir: müvafiq zirvənin yüksəklik səviyyəsi və daha yüksək bir zirvəyə gedən yolda mümkün olan ən yüksək ən aşağı nöqtənin yüksəklik səviyyəsi. Zirvələr haqqında məlumat onların yüksəklik səviyyəsinə görə azalan sırada yazılmalıdır; əgər bir neçə zirvə eyni yüksəklik səviyyəsinə malikdirsə, onlar ən aşağı nöqtənin yüksəklik səviyyəsinə görə azalan sırada sıralanmalıdır.
Misal üçün şərh 1:
Bütün zirvələr dairələrlə işarələnmişdir. 15 yüksəklik səviyyəsinə malik zirvədən mümkün yollardan biri tünd rənglə göstərilmişdir.