Minimize Maximum Distance by Adding One Colored Source

Given an n × m grid with k initially colored cells, you may choose exactly one additional cell to be a new colored source. Movement is allowed in all 8 directions: up, down, left, right, and the four diagonals. Each move has cost 1. The inconvenience of a cell is the shortest-path distance from that cell to its nearest colored source, including both initially colored cells and the newly added source. Return the minimum possible value of the maximum inconvenience over all cells after adding one source optimally. Input Format First line: three integers n m k n: number of rows m: number of columns k: number of initially colored sources Next k lines: two integers r c, denoting a source position using 1-indexed coordinates. Output Format Print one integer: the minimum possible maximum inconvenience. Constraints 1 ≤ n, m 1 ≤ k ≤ n × m Initial source positions are distinct. For an efficient implementation, assume n × m ≤ 2 × 10^5. Example 1 Input: 3 3 1 2 2 Output: 1 Example 2 Input: 3 3 1 1 1 Output: 2 Explanation: A source can be added at (3, 3), but cells such as (1, 3) and (3, 1) still have distance 2 from their nearest source. Example Input 3 3 1 2 2 Output 1