Автобус

Щоранку Антон їде на роботу автобусом.

Маршрут автобуса включає $n$ зупинок, пронумерованих від $1$ до $n$ в порядку прямування. Автобус проїжджає від кожної зупинки до наступної за одну хвилину, а його стоянки можна знехтувати. Антон сідає на першій зупинці і виходить на останню.

В автобусі є $m$ сидінь, які розташовані в один ряд і пронумеровані від $1$ до $m$, найближче до входу сидіння має номер $1$, а найдальше — номер $m$. На кожному сидінні може сидіти один пасажир, а біля кожного сидіння може стояти один пасажир. Коли людина входить до автобуса, вона сідає на найближче до входу вільне сидіння. Якщо вони всі зайняті, він шукає найближче до входу сидіння, поряд з яким ніхто не стоїть, і встає у людини, яка там сидить над душею. Якщо такого місця немає, він виходить із автобуса.

Кожен пасажир залишається на своєму місці до прибуття на потрібну йому зупинку. Пасажир, що стоїть, залишається стояти, навіть якщо якесь сидіння звільнилося.

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

Антон зайшов до автобуса першим, він може сісти на будь-яке сидіння і залишитися на ньому до кінця поїздки. Він добре знає, хто ще їхатиме в автобусі, про кожного пасажира Антон знає, на якій зупинці той увійде до автобуса і на який вийде. Допоможіть Антону вибрати місце так, щоб під час поїздки у нього якнайменше сумарно стояли над душею.

Вхідні дані

У першому рядку вхідних даних задані три цілих числа $n,m$ та $k(2\le n\le 10^9,1\le m\le 2\cdot 10^5,0\le k\le 2\cdot 10^5)$ — кількість зупинок, кількість сидінь в автобусі та кількість пасажирів, крім Антона.

У наступних $k$ рядках задано по два числа $a_i$ та $b_i$, які означають, що $i$-й пасажир збирається увійти на $a_i$ -й зупинці і вийти на $b_i$-й ($1\le a_i<b_i\le n)$.

Якщо на одній зупинці в автобус заходить кілька людей, вони заходять у порядку, в якому вони перераховані у вхідних даних.

Вихідні дані

Виведіть два числа на одному рядку — мінімальний сумарний час у хвилинах, протягом якого Антон стоятиме над душею, і номер місця, на яке для цього потрібно сісти. Якщо таких місць є кілька, виведіть найближче до входу.

Приклади