Several months ago, Peer was painting triangles on a canvas from the outside in. Now that triangles are out and squares are in, his newest paintings use concentric squares, and are created from the inside out! Peer starts painting on a rectangular canvas divided into a perfect square grid. He selects a number of single grid cells to act as central seeds, and paints them with the darkest shade. From each of the seed squares, Peer paints a larger square using a lighter shade to enclose it, and repeats with larger squares to enclose those, until the entire canvas is covered. Each square is exactly one grid cell larger and one shade lighter than the one it encloses. When squares overlap, the grid cell is always filled using the darker shade.


Each test case begins with a single line containing three integers, m, n, and s, separated by spaces. The canvas contains exactly m x n grid cells (1 ≤ m, n ≤ 1,000), numbered 1, . . . ,m vertically and 1, . . . , n horizontally. Peer starts the painting with s (1 ≤ s ≤ 1,000) seed cells, described on the following s lines of text, each with two integers, ri and ci (1 ≤ rim, 1 ≤ cin), describing the respective grid row and column of each seed square. All seed squares are within the bounds of the canvas.

For example, the input for the test case shown in the figure above, would look like:

10 8 3
3 3
7 7
10 2


For each test case, your program should print one integer on a single line: the number of different shades required for the painting described.

Output corresponding to the sample input would appear as such:


Submitting to 'boundlessboxes'

You're not logged in! Click here to login

Submitting .cpp to 'boundlessboxes'

You're not logged in! Click here to login

Compile Errors

Time Limit: 1 Seconds
Memory Limit: 512MB
No. of ACs: 70
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0