A community art collective is repainting a large rectangular mural made of a grid with R rows and C columns of cells (rows and columns are 0-indexed). Every cell starts with zero coats of paint. The collective then performs a sequence of painting passes. Pass i is described by two integers r_i and c_i, and adds exactly one coat of paint to every cell that lies within the top-left-anchored rectangle spanning rows 0 through r_i - 1 and columns 0 through c_i - 1. After all passes have been applied, determine how many cells in the mural carry the maximum number of paint coats found anywhere on the mural (if no passes are performed, every cell has 0 coats, and every cell counts toward the maximum).
The first line contains three integers R, C, and P — the number of rows, the number of columns, and the number of painting passes. Each of the next P lines contains two integers r_i and c_i describing one painting pass.
Print a single integer: the number of cells that carry the maximum number of paint coats after all P passes.
Example 1
Input
3 3 2 2 2 3 3
Expected
4
Explanation
The first pass covers rows 0-1 and columns 0-1 (a 2x2 block), adding one coat there. The second pass covers the entire 3x3 grid, adding one more coat everywhere. After both passes, the 2x2 block in the top-left corner has received 2 coats (the maximum), while every other cell received only 1 coat. There are 2*2 = 4 cells with the maximum, so the answer is 4.
Example 2
Input
3 3 0
Expected
9
Explanation
No painting passes are performed, so every one of the 3*3 = 9 cells remains at 0 coats. Since 0 is the maximum coat count present, all 9 cells qualify, so the answer is 9.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →