Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


3. Бимедиатека

Автор задачи: Купрейчик Антон
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 1 с.
Ограничение по памяти: 128 МБ

Однажды программист Иван захотел посмотреть очередную серию своего любимого сериала «Игра стульев». Он зашел на сайт «Бимедиатека» (именно этот сайт официально локализует сериал в нашей стране) и включил воспроизведение новой серии. Но, как всегда, возникли трудности — скорости передачи данных (она же — скорость интернет-соединения Ивана) не хватало чтобы воспроизводить видео с выбранным битрейтом без временных остановок воспроизведения (для «подкачки» видео). Иван — не простой человек, он — программист, а потому он решил узнать, какое минимальное целое количество времени w в секундах ему следует подождать перед началом воспроизведения видео, чтобы воспроизведение могло быть выполнено без единой остановки для «подкачки» видео.

Ваша задача — написать программу, которая по заданной зависимости скорости интернет-соединения от времени определит искомое количество времени w.

Входные данные

В первой строке входных данных содержатся два целых числа b и tm — битрейт видео (в кбит/с) и продолжительность видео в минутах соответственно (1 ≤ b ≤ 216, 1 ≤ tm ≤ 104). Далее следует описание зависимости скорости интернет-соединения от времени: в первой строке этого описания задано целое число n — количество временных интервалов в распределении (1 ≤ n ≤ 105). Следующие n строк описания содержат по два целых числа ti и si — время конца i-го интервала в секундах и скорость интернет-соединения (в кбит/с) в этот момент времени соответственно (1 ≤ ti ≤ 6·105, 0 ≤ si ≤ 216). Моменты времени ti строго упорядочены по возрастанию. Считается, что в момент времени 0 битрейт был так же равен нулю. Между любой парой соседних значений времени скорость интернет-соединения линейно изменяется от уровня этой скорости в первый момент времени до уровня во второй момент времени. Начиная с момент времени tn, скорость интернет-соединения остается неизменной и равной sn. Гарантируется, что sn > 0.

Выходные данные

Единственная строка выходных данных должна содержать ровно одно целое число w — минимальное необходимое количество секунд. Обратите внимание, что Иван может включить видео только через целое количество секунд, следовательно, ответ всегда является целым.

Примеры
Стандартный вводСтандартный вывод
1024 100
9
10 400
20 800
30 1600
40 1200
50 1600
60 1200
70 1600
80 1200
90 1600
13