题目描述

译自 ROIR 2017 Day2 T3. Силовые поля

在物理生物实验室中，研究人员正在研究通过力场对植物进行辐射的影响。

实验装置包含一个大小为 $10^{9} \times 10^{9}$ 的正方形平台，平台上充满肥沃土壤。平台上方安装有辐射源。在辐射源和平台之间可以启用 $n$ 个力场。

力场发生器安装在坐标 $(0, 0)$ 上方。第 $i$ 个力场是一个矩形，其边与平台边界平行，且两个相对角的坐标为 $(0, 0)$ 和 $(x_i, y_i)$。

在实验中，计划研究通过 $k$ 个力场对植物进行辐射的影响。需要从给定的 $n$ 个力场中选择 $k$ 个用于实验。科学家希望选择力场的方式，使得平台上被所有 $k$ 个所选力场覆盖的区域面积最大。

你的任务是编写一个程序，根据给定的整数 $n, k$ 以及 $n$ 个力场的描述，确定选择哪些 $k$ 个力场进行实验，以便所有 $k$ 个力场覆盖的区域面积最大，并输出该区域的面积。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $k$ $(1 \leq k \leq n \leq 200000)$，分别表示力场的总数和需要选择用于实验的力场数量。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ $(1 \leq x_i, y_i \leq 10^{9})$，表示第 $i$ 个力场远离坐标原点的角的坐标。

输出格式

输出一个整数，表示所需区域的最大面积。

5 3
3 5
2 2
2 5
4 4
5 3

9

在图 1 中展示了输入数据中描述的五个力场。图 2 中展示了从五个力场中选择三个进行实验的最佳方式。

详细子任务附加限制及分值如下表所示：