Задача №111534. Событие
В Москве происходит Важное Событие. Посмотреть на Важное Событие съехалось множество людей со всей страны. Во избежание давки и соблюдения порядка полицией была организована очередь, растянувшаяся по набережной Москвы-реки от станции метро X аж до станции метро Y!
Вся очередь разделена на N секторов с помощью перегородок с турникетами. Вход на Важное Cобытие расположен перед первой перегородкой, т.е. попасть туда можно только из сектора 1.
Раз в секунду через каждую перегородку, перед которой есть хотя бы один человек, в сторону События через турникет пропускают одного человека (то есть из сектора i в сектор i - 1, и из сектора 1 — на само Событие). Внутри сектора люди передвигаются существенно быстрее, поэтому этим временем можно пренебречь.
По известному количеству людей в секторах определите, через сколько секунд на Важное Событие попадет последний человек.
В первой строке заданы число секторов N и число непустых секторов M (1 ≤ N ≤ 109, 0 ≤ M ≤ 105). В следующих M строках записаны числа ai и bi — номер i-того непустого сектора и bi — количество человек в нем (1 ≤ a1 < a2 < ... < aM ≤ N, 1 ≤ bi ≤ 109)
Выведите одно целое число — время в секундах, через которое все люди смогут попасть на Важное Событие.
3 2
1 1
3 2
4
3 2
2 2
3 2
5
Тесты состоят из четырёх групп.
- Тесты 1–2, из условия, оцениваются в 0 баллов.
- В тестах этой группы N ≤ 1 000, и общее количество людей во всех секторах также не превосходит 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы N ≤ 105, общее число людей тоже не превосходит 105. Эта группа оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
- Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый тест оценивается независимо от других.