Автобус

Каждое утро Антон едет на работу на автобусе. Маршрут автобуса включает в себя N остановок, пронумерованных от 1 до N в порядке следования. Автобус проезжает от каждой остановки до следующей за одну минуту, а его временем стоянки можно пренебречь. Антон садится на первой остановке и выходит на последней.

В автобусе есть M сидений, которые расположены в один ряд и пронумерованы от 1 до M, ближайшее к входу сиденье имеет номер 1, а самое дальнее – номер M. На каждом сиденье может сидеть один пассажир, а также возле каждого сиденья может стоять один пассажир.

Когда человек входит в автобус, он садится на ближайшее от входа свободное сиденье. Если они все заняты, он ищет ближайшее от входа сиденье, рядом с которым никто не стоит, и встаёт у сидящего там человека над душой. Если такого места нет, он выходит из автобуса.

Каждый пассажир остаётся на своём месте до прибытия на нужную ему остановку. Стоящий пассажир остаётся стоять, даже если какое-то сиденье освободилось.

На каждой остановке из автобуса сначала выходят все пассажиры, которые собирались выйти на этой остановке, и только потом заходят новые.

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

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

В первой строке входного файла INPUT.TXT заданы три целых числа N, M и K – количество остановок, количество сидений в автобусе и количество пассажиров, кроме Антона (2 ≤ N ≤ 10⁹, 1 ≤ M, K ≤ 2×10⁵).

В следующих K строках задано по 2 числа a_i и b_i, которые означают, что i-й пассажир собирается войти на a_i-й остановке и выйти на b_i-й (1 ≤ a_i < b_i ≤ N).

Если на одной остановке в автобус заходит несколько человек, они заходят в том порядке, в котором они перечислены во входных данных.

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

В выходной файл OUTPUT.TXT выведите два числа на одной строке – минимальное суммарное время в минутах, в течение которого у Антона будут стоять над душой, и номер места, на которое для этого нужно сесть. Если таких мест несколько, выведите ближайшее место от входа.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!