Вершины
Альпинист, живущий на гористом острове, поднялся на одну из вершин и теперь стремится достичь более высокой вершины.
Каждая точка на острове имеет положительную высоту над уровнем моря (высота моря равна 0). Если текущая вершина, на которой находится альпинист, имеет высоту E_i, то его цель — достичь вершины с высотой E_j (E_j > E_i). Поскольку он находится на вершине, прямого пути вверх нет — чтобы подняться на более высокую точку, альпинисту сначала нужно спуститься на более низкий уровень, а затем снова подняться. Спуск не так значителен, как подъем, поэтому альпинист хочет максимизировать высоту самой низкой точки на пути от текущего местоположения к более высокой вершине.
Например, если профиль острова показан на рисунке, и альпинист находится на вершине с высотой E_4, то есть три вершины с большей высотой (E_5, E_6 и E_7), но путь с самой низкой точкой, имеющей наибольшую высоту, — это путь к вершине с высотой E_7 — на этом пути он никогда не опускается ниже уровня E_2 (в других случаях он будет вынужден спуститься до уровня E_1). Если бы он начал с E_5, соответствующий самый низкий уровень был бы E_3 (путь к E_6), но если бы он начал с E_6, это был бы E_1.
Карта острова представлена двумерной прямоугольной таблицей размером N×M, описывающей высоту различных частей острова — число в ячейке указывает высоту соответствующего региона. Две ячейки считаются смежными, если они имеют общую точку. Таким образом, каждая ячейка (кроме тех, что на границе) смежна с восемью другими. Путь — это последовательность ячеек, где каждая пара последовательных ячеек является смежной. Плоская область — это набор из одной или более ячеек с одинаковой высотой, любая пара которых соединена путем, проходящим только через ячейки внутри набора. Любые две смежные ячейки с равной высотой принадлежат одной и той же плоской области. Вершина — это плоская область, ячейки которой не имеют смежных ячеек с большей высотой.
Напишите программу, которая находит все вершины на острове и для каждой из них определяет высоту самой высокой возможной низкой точки на пути к какой-либо вершине с большей высотой. Для самой высокой вершины на острове (для которой нет более высокой вершины на этом острове) предполагается, что альпинист покинет остров в поисках более высоких вершин, таким образом, самая низкая точка будет 0 (уровень моря).
Входные данные
Первая строка входного файла содержит два положительных целых числа N и M (1 ≤ N, M ≤ 2000, N×M ≤ 10^5), высоту и ширину карты соответственно. Следующие N строк содержат описание карты острова. Каждая из этих строк содержит M целых чисел E_ij (1 ≤ E_ij ≤ 10^6), разделенных пробелами. Высота ячейки E_ij (соответствующей i-й строке и j-му столбцу на карте) дана как j-е число в i+1-й строке файла.
Выходные данные
Первая строка выходного файла должна содержать одно целое число P, количество найденных вершин на острове. Следующие P строк должны содержать по два целых числа: высоту конкретной вершины и высоту самой высокой возможной низкой точки на пути к какой-либо более высокой вершине. Информация о вершинах должна быть записана в порядке убывания их высоты; если несколько вершин имеют одинаковую высоту, то они должны быть отсортированы в порядке убывания высоты низкой точки.
Комментарий к примеру 1:
Все вершины отмечены кругами. Один из возможных путей от вершины с высотой 15 показан темной окраской.