Tor Colonization
Limits: 2 sec., 256 MiB
Some time ago humans colonized a torus planet with huge oil fields left by klaxosaurs. Many billionaires invested in developing energy infrastructure on this planet. In a few years, people have built a lot of energy farms all over the place. As oil mining uses dangerous technologies, the location of farms must have satisfied the safety rules. If we imagine the planet surface as a grid with a size \(n\) by \(m\) squares, each farm takes exactly \(2\) by \(2\) space, and no two farms can have common points. Needless to say that the grid is cyclic vertically and horizontally so the first and the last rows are adjacent and same for the first and the last column.
As time goes on, technologies change too. Recently a new method to mine oil was discovered, which is much safer than the previous one. Investors want to get maximum profit from this technology, so they decided to cover the whole planet with farms. It is possible to do so because \(n\) and \(m\) are even. The only problem is the location of already built farms. It is not cost-effective to destroy those farms, but you can move them. It cost one bitcoin to move a farm by one unit in one of four directions. After rearrangement all free space must be coverable with \(2\) by \(2\) squares without any overlap area and old farms couldn’t also overlap.
Find the minimum amount of bitcoins needed to rearrange farms. Keep in mind that the grid is cyclic in both directions. Old farms are using new technology now, so they can touch each other while being moved.
Input
The first line contains two integers \(m\) and \(n\) – width and height of the grid.
Second line contains one integer \(k\) – number of farms.
Each of the following \(k\) lines contains two integers \(x_i\) and \(y_i\) – the coordinates of the center of the \(i\)-th farm. No two farms have common points.
Output
Print one integer – minimum amount of bitcoins.
Constraints
\(4 \le m, n \le 10^{5}\), \(n\) and \(m\) are even,
\(1 \le k \le 10^{5}\),
\(1 \le x_{i} \le m\),
\(1 \le y_{i} \le n\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 4 1 2 3 | 0 |
Input (stdin) | Output (stdout) |
---|---|
12 6 8 2 1 2 4 5 1 5 4 8 6 8 3 11 6 11 3 | 6 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|