Amazon is introducing an innovative smart canvas display for personalized home decor. The canvas is initially painted white, featuring n rows and m columns, waiting to be transformed into a beautiful masterpiece. Each minute, the canvas undergoes a unique coloring process as specified by the user.
A beautiful canvas is defined by the presence of a square with a side length of k where all cells within the square are elegantly colored.
Determine the minimum time required for the canvas to achieve its beauty.
Formally, Given n and m that denote the number of rows and columns of the canvas respectively, k denotes the size of the square, and a 2D array paint of dimensions (n * m) rows and 2 columns, where each entry (paint[i][0], paint[i][1]) represents the coordinates of a cell to be painted black during the ith minute.
Note that each cell is painted only once during this transformation.
Find the minimum time (in minutes) after which the canvas becomes beautiful.
Example 1:
Input: n = 2, m = 3, k = 2, paint = [[1, 2], [2, 3], [2, 1], [1, 3], [2, 2], [1, 1]]
Output: 5
Explanation:After the 5th and 6th minutes, the canvas has a square of size 2*2 with all black cells starting at position (1, 2) at minute 5, and two squares at (1,1) and (1,2) at minute 6, so the minimum time after which the canvas becomes beautiful is 5 minutes.
1 ≤ n, m ≤ 7501 ≤ k ≤ min(n, m)1 ≤ paint[i][0] ≤ n1 ≤ paint[i][1] ≤ mpaint[i] ≠ paint[j]for any1 ≤ i < j ≤ n*m
input:
output: