Колонізація тора
Обмеження: 2 сек., 256 МіБ
Колись дуже давно людям удалося колонізувати тороїдальну планету з величезними нафтовими покладами, залишеними клаксозаврами. Багато мільярдерів інвестували в розвиток енергетичної промисловості на цій планеті. Через кілька років було збудовано величезну кількість нафтових станцій по всій планеті. Оскільки видобування нафти — доволі небезпечна робота, розташування станцій повинне задовольняти правила безпеки. Якщо уявити поверхню планети як сітку розміром \(n\) на \(m\) квадратів, то кожна станція займає рівно 2 на 2 місця, і жодні дві станції не мають спільних точок. Варто зазначити, що сітка буде зацикленою вертикально й горизонтально, отже перший і останній рядок є суміжними, аналогічно для стовпчиків.
Час ішов, технології мінялись... Нещодавно відкрили новий метод видобування нафти, який є набагато безпечніший та дешевший за попередній. Інвестори хочуть отримати максимальний прибуток із цього відкриття й вирішили покрити всю планету нафтовими станціями. Це можливо, оскільки \(n\) i \(m\) парні. Єдина проблема — це розташування наявних станцій. Знищувати теперішні станції дуже дорого, проте дешево попросити інженерів транспортувати їх на нові локації. Під час пересування станції можуть дотикатись, але не перетинатись. Ціна пересування станції на одиницю в одному із чотирьох напрямків — 1 біткоїн. Після пересування ви повинні могти ідеально покрити всі порожні ділянки новими станціями.
Знайдіть мінімальну кількість біткоїнів, яка потрібна для реалізації плану. Не забувайте про те, що сітка циклічна в обох напрямках.
Вхідні дані
Перший рядок містить два цілих числа \(m\) and \(n\) — ширину й висоту сітки.
Другий рядок містить ціле число \(k\) — кількість станцій.
Кожен із наступних \(k\) рядків містить по два цілих числа \(x_i\) та \(y_i\) — координати центра \(i\)-ої станції. Жодні дві станції не мають спільних точок.
Вихідні дані
В одному рядку виведіть ціле число — мінімальну кількість біткоїнів.
Обмеження
\(4 \le m, n \le 10^{5}\),
\(n\) і \(m\) парні,
\(1 \le k \le 10^{5}\),
\(1 \le x_{i} \le m\),
\(1 \le y_{i} \le n\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 2 3 | 0 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
12 6 8 2 1 2 4 5 1 5 4 8 6 8 3 11 6 11 3 | 6 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|