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


5. Рапунцель

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

У Рапунцель очень длинные волосы. Она заточена в высокой башне посреди волшебного леса, поэтому самостоятельно не может выбраться из башни. Много принцев из разных королевств наслышаны о красоте Рапунцель и хотят освободить ее. Для того чтобы освободить Рапунцель, принц должен попасть к ней на вершину башни.

Отыскать место заточения в волшебном лесу довольно трудно, поэтому лишь один принц в день добирается до башни, и то к самому вечеру. Когда очередной принц подходит к башне Рапунцель, она спускает ему свои волосы, и принц пытается забраться по ним на вершину башни. Чтобы принц смог забраться по волосам Рапунцель, ему необходимо дотянуться до них. Известно, что башня имеет фиксированную высоту h единиц, а у каждого принца свой рост li единиц. Утром i-го дня длина волос Рапунцель увеличивается на di единиц. Изначально длина ее волос равна s.

В башне очень мало места, и длинные волосы мешают Рапунцель, поэтому она хочет их укоротить. Определите, на какую максимальную длину может укоротить волосы Рапунцель утром первого дня, чтобы ее смог спасти хотя бы один принц.

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

В первой строке входных данных записано три целых числа h, s и n — высота башни, начальная длина волос Рапунцель и количество принцев, которые собираются спасти Рапунцель соответственно (1 ≤ h, s ≤ 108, 1 ≤ n ≤ 105).

Каждая из последующих n строк описывает очередной день — i-я строка описывает i-й по порядку день, двумя целыми числами li и di — высотой пришедшего принца и изменением длины волос Рапунцель в этот день соответственно (1 ≤ li, di ≤ 104).

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

В единственной строке выходных данных требуется вывести одно целое число — искомую максимальную длину, на которую можно укоротить волосы Рапунцель, чтобы хотя бы один из принцев смог ее спасти. В случае, если даже с нетронутыми волосами Рапунцель не может быть спасена ни одним из принцев, выведите «R.I.P.» (без кавычек).

Примеры
Стандартный вводСтандартный вывод
21 10 3
3 2
6 4
1 1
1
100 10 2
10 10
11 20
R.I.P.