12. Пробежка по холмам (20 баллов)

Уже знакомый вам абитуриент Вася, покончив с окраской забора, осмотрелся - и был поражен удивительной красотой местных пейзажей. Особенно ему понравились холмы: по ним он регулярно совершал пробежки, последовательно посещая одни и те же n холмов. Вася заметил, что перепады между соседними вершинами на его трассе небольшие, не более 1 метра, т.е. для всех холмов с номерами от 1 до n-1 выполнено условие: модуль разности высот этого холма и следующего не больше 1. Для поддержания интеллектуального тонуса Вася решил записать высоты всех n вершин холмов в свою тетрадь.

В тот день когда Вася закончил свои записи, он забыл тетрадку на крыльце, и, конечно же, пошел дождь. Он – ну вы уже догадались, - смыл некоторые записи и исказил некоторые цифры. Вася обнаружил это только тогда, когда вернулся домой в Питер с высушенной тетрадью, и ему стало интересно: какова могла быть высота самого высокого холма, исходя из оставшихся записей. Помогите по имеющимся записям восстановить максимальное возможное значение высоты, либо определите, что записи исказились настолько, что не соответствуют никаким возможным значениям высот, удовлетворяющим заданным ограничениям.

Входные данные: В первой строке через пробел записано два натуральных числа n и m (n≤10⁸, m≤10⁵) — количество вершин холмов и количество сохранившихся записей в тетради. В следующих m строках через пробел записано по два натуральных числа d и h_d, номер холма (нумерация с 1) и высота холма с этим номером, h_d≤10⁸.

Выходные данные: Если записи не противоречивы, выведите одно целое число — максимально возможное значение высоты. Если же записи не согласуются ни с каким вариантом значений высот, выведите одно слово «NO».