P5896 [IOI 2016] aliens

我们的卫星刚刚通过观测一个遥远的星球发现了外星文明。我们也已经获得了该星球的一个正方形区域的低分辨率照片。这个照片上有许多智能生命的迹象。专家们也已经确定了照片上的 $n$ 个兴趣点。这些兴趣点被编号为 $0$ 到 $n−1$。现在我们希望拍摄一些能包含全部 $n$ 个兴趣点的高分辨率照片。 卫星已将低分辨率照片的区域划分成由 $m \times m$ 个单位正方形的小方格组成的网络。网格的行和列被连续地编号为 $0$ 到 $m−1$（从上到下和从左到右）。我们用坐标 $(s,t)$ 来表示第 $s$ 行与第 $t$ 列上的小方格。第 $i$ 个兴趣点位于小方格 $(r_i,c_i)$ 上，每个小方格子上可以包含任意多个兴趣点。 卫星在一个固定的轨道上运行，而它刚好也直接经过这个网格的主对角线的上方。主对角线就是指在网络中连接左上角和右下角的那条线段。卫星能够在任意的区域上拍摄高分辨率的照片，但必须满足以下条件： - 拍摄的区域必须是正方形。 - 这个正方形的两个对角（注：变通理解为主对角线）全部包含在网格的主对角线中。 - 网格中的每个小方格或者完全在拍摄范围内，或者完全在拍摄范围外。 卫星最多只能拍摄 $k$ 张高分辨率照片。 一旦卫星拍摄完成，它将把每个拍摄区域的高分辨率照片传送到地面基站（无论这些区域是否包含兴趣点）。尽管一个小方格可能会被多次拍摄，但每个被拍摄到的小方格上的数据只会被传送一次。 因此，我们必须选择最多 $k$ 个正方形区域进行拍摄，而且要保证： - 每个包含至少一个兴趣点的小方格必须被至少拍摄到一次 - 被拍摄到至少一次的小方格数目必须是最小的。 你的任务就是去找出被拍摄到的小方格有可能的最小值。

无

无

**子任务** 在全部子任务中， $1\le k\le n$。 | 子任务 | 分数 | $n\le$ | $m\le$ | 其他限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $4$ | $5$ | $100$ | $k=n$| | $2$ | $12$ | $500$ | $10^3$ | $r_i=c_i$ | | $3$| $9$ | $500$ | $10^3$ | 无 | |$4$ |$16$ | $4 \times 10^3$ | $10^6$ | 无 | | $5$ | $19$ | $5\times 10^4$ | $10^6$ | $k \le 100$ | | $6$ | $40$| $10^5$ | $10^6$ | 无 |