Майстер Уґвей#10673

Майстер Уґвей

0,5 секунди

64 мегабайти

Дуже легка

Коли Бариш вступив до Массачусетського технологічного інституту, він взяв із собою свою черепаху Уґвей. Майстер Уґвей - надзвичайно розумна черепаха, і, як і його власник Бариш, він захоплюється розв'язуванням алгоритмічних задач, куди б він не пішов. Під час прогулянки по території Массачусетського технологічного інституту, Бариш і Уґвей натрапили на прямокутну ділянку розміром $n \times m$ n \times m, розділену на клітини. У цій ділянці верхня ліва клітина позначена як $(1, 1)$ , а нижня права - як $(n, m)$ . Щоб перевірити інтелект Уґвея, Бариш розмістив монети на певних клітинах, і Уґвей, починаючи з клітини $(1, 1)$ , повинен зібрати ці монети, рухаючись лише вправо або вниз. Зрозуміло, що в деяких випадках неможливо зібрати всі монети за один раз. Тому вони приходять на цю ділянку щодня, і Уґвей, починаючи з клітини $(1, 1)$ , щодня збирає певну кількість монет. Бариша цікавить, за яку мінімальну кількість днів Уґвей зможе зібрати всі монети.

Вхідні дані

Перший рядок містить два цілі числа $n$ ( $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^{9}) і $m$ ( $1 \leq m \leq 1 0^{9}$ 1 \leq m \leq 10^{9}) - кількість рядків і стовпців у прямокутній ділянці відповідно. У другому рядку вказано ціле число $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \leq q \leq 10^{5}) - кількість монет. У кожному з наступних $q$ рядків наведені координати клітин, де розміщені монети, у вигляді двох цілих чисел $x_{i}$ x_i ( $1 \leq x_{i} \leq n$ 1 \leq x_i \leq n) і $y_{i}$ y_i ( $1 \leq y_{i} \leq m$ 1 \leq y_i \leq m). Усі монети розташовані в різних клітинах.

Вихідні дані

Виведіть одне ціле число - мінімальну кількість днів, необхідну для збирання всіх монет.

Приклади

Приклад 1

Примітка

Ділянка, наведена в прикладі:

Переміщення Уґвея в перший день можуть виглядати так, як показано нижче:

Переміщення Уґвея на другий день можуть виглядати так, як показано нижче:

Оцінювання

Завдання складається з наступних $5$ підзадач: