Задачи
Мастер Угвэй
Мастер Угвэй
Когда Барыш пошел учиться в Массачусетский технологический институт, он взял с собой свою черепаху Угвэй. Мастер Угвэй - очень умная черепаха, и, как и ее владелец Барыш, он любит решать алгоритмические задачи, куда бы он ни пошел.
Прогуливаясь по двору Массачусетского технологического института, Барыш и Угвэй увидели прямоугольную область размером $(n,m)$ , разделенную на клетки. В этой области мы обозначим верхнюю левую клетку $(1,1)$ и нижнюю правую клетку $(n,m)$.
Чтобы проверить интеллект Угвэя , Барыш разместил монеты на определенных клетках и Угвэй начиная с клетки $(1,1)$ с каждым шагом вправо или вниз должен собрать эти монеты . Ясно ,что будет случай когда невозможно будет собрать все монеты . Поэтому они приходят в это место каждый день и Угвэй один раз в день начиная с клетки $(1,1)$ двигается и собирает определенное количество монет.
Барыша беспокоет один вопрос , за какое минимальное количество дней Угвэй сможет собрать все монеты .
\subsection{\bfseries{Входные данные}}
Первая строка содержит два целых числа $n$ ( $1 \leq n \leq 10^{9}$ ) и $m$ ( $1 \leq m \leq 10^{9}$ ) - количество строк и столбцов в прямоугольной области соответственно. Во второй строке целое число - количество монет. В каждой из следующих $q$ ( $1 \leq q \leq 10^{5}$ ) строк даны координаты клеток с двумя целыми числами $x_i$ ( $1 \leq x_i \leq n$ ) и $y_i$ ( $1 \leq y_i \leq m$ ) . Все монеты находятся в разных клетках.
\subsection{\bfseries{Выходные данные}}
Выведите одно целое число - минимальное количество дней, необходимое для сбора всех монет.
\subsection{\bfseries{Подзадачи}}
Данная задача состоит из нижеследующих $5$ подзадач:
\includegraphics{https://static.e-olymp.com/content/09/091d759b8dc8b3a911fe5297302c142a3e03e719.png}
\subsection{\bfseries{Пояснение к примеру}}
Область данная в примере: \par
\includegraphics{https://static.e-olymp.com/content/22/224205eb1d190594b92af4fd952e6b2336abf0fb.png}
Передвижения Угвэя в первый день могут быть так как показано внизу: \par
\includegraphics{https://static.e-olymp.com/content/41/413550ef96c52fcd02531ee6b542aa888c996572.png}
Передвижения Угвэя во второй день могуть быть так как показано внизу: \par
\includegraphics{https://static.e-olymp.com/content/1c/1c59f29529cd94b9b151858b9c93ee779fdf149b.png}
Входные данные #1
3 3 4 1 2 2 2 1 3 3 2
Выходные данные #1
2