P11104 [ROI 2023] Monitoring (Day 1)

Translated from [ROI 2023 D1T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。 The security of the shopping mall building is ensured by a video surveillance system。 On the security staff’s computer there is a program that shows videos from multiple cameras on the screen。The program works as follows： A rectangular grid with $h$ rows and $w$ columns is shown on the screen。Each cell can be empty, or it can show the image from some camera。To control the positions of images in the program, the security staff can use the “Left”, “Right”, “Up”, and “Down” buttons。 - Pressing “Left” moves the image in each cell to the cell to its left。Images in the leftmost column are moved to the corresponding cells in the rightmost column。 - Pressing “Right” moves the image in each cell to the cell to its right。Images in the rightmost column are moved to the corresponding cells in the leftmost column。 - Pressing “Up” moves the image in each cell to the cell above it。Images in the top row are moved to the corresponding cells in the bottom row。 - Pressing “Down” moves the image in each cell to the cell below it。Images in the bottom row are moved to the corresponding cells in the top row。 The rows of the grid are numbered from top to bottom, and the columns from left to right。$(r, c)$ denotes the cell in row $r$ and column $c$。 Below is an example of a grid with $3$ rows and $4$ columns and three cells containing images, with coordinates $(1, 1),(2, 4),(3, 3)$。It also shows the new positions of the images after pressing the four buttons。 

The security staff want the cells showing images on the screen to be as compact as possible。The compactness of the images can be measured by the area of the smallest rectangle in the grid that contains all displayed images。Pressing buttons can change the compactness。For example, in the figure below, the initial layout has compactness $12$。After pressing “Right” once and “Up” once, the compactness becomes $4$。  Given a grid containing $k$ images, compute the minimum compactness that can be achieved using the “Left”, “Right”, “Up”, and “Down” buttons, and also compute the minimum number of button presses needed to achieve this minimum compactness。

The first line contains three integers $h,w,k$, representing the size of the grid and the number of cells containing images ($1 \le h, w \le 10^9;1 \le k \le 100,000$)。 Each of the next $k$ lines contains two integers $r_i$ and $c_i$, denoting the coordinates of a cell containing an image ($1 \le r_i \le h$; $1 \le c_i \le w$)。It is guaranteed that all $k$ cell coordinates are distinct。

Output two integers: the minimum image compactness achievable using the buttons, and the minimum number of button presses required to achieve that compactness。

| Subtask | Score | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $5$ | $k=1$ | | $2$ | $10$ | $k=2$ | | $3$ | $29$ | $h=1$ | | $4$ | $11$ | $h,w\le50$ | | $5$ | $15$ | $h,w\le1000$ | | $6$ | $6$ | $h,w\le200000$ | | $7$ | $24$ | None | Translated by ChatGPT 5