bleak plume
I tried but can't solve it. pls help.
Problems:
PHOTOGRAPHY
An area is represented by a square grid of size m x m. The rows are numbered from 1 to m from top to bottom, the columns are numbered from 1 to m from left to right. The intersection of row x and column y is cell (x, y). There are n objects of interest, the i-th object (1 ≤ i ≤ n) is located in cell (xi, yi). A satellite moves in an orbit on the main diagonal of the grid (the diagonal connecting the upper left corner with the lower right corner of the grid). The satellite can take at most k pictures, each picture is an arbitrary region satisfying:
- ✓ The shape of the region is square;
- ✓ The upper left and lower right corners of the square lie on the main diagonal of the grid;
- ✓ Each grid cell lies either completely inside or completely outside the captured area.
Task: Select no more than k square regions corresponding to the satellite images so that each object belongs to at least one captured region and the number of grid cells located in the captured regions is minimal.
Input:
- The first line is 3 intergers n, m, k (k ≤ 5000; k ≤ n)
- The i-th line (1 ≤ i ≤ n) in n lines have 2 intergers x-i and y-i (1 ≤ xi, yi, ≤ m)
Output:
- Only 1 line print the least number of cells belonging to the captured area
Example:
Input:
5 4 3
1 1
2 3
3 3
2 3
3 4
Output:
8
coarse ermine