P7371 [COCI 2018/2019 #4] Kisik
题目描述
CAIN 组织决定建立为 $K$ 个家庭在火星上一个新的小镇，因此将建立 $K$ 幢楼房，每家一幢。对于每个家庭，CAIN 提供了 $N$ 种不同的楼房设计可供选择。
楼房都互相紧挨着，以便让它们底部在同一直线上。在建设之后，城市需要进行充气，并让其保存在一个玻璃墙内。玻璃墙只能围住一片矩形区域，因此充气的范围也是一个矩形区域。
求出所需最少的充气量。
输入格式
第一行输入整数 $N,K$。
接下来的 $N$ 行，每行输入整数 $W_i,H_i$，表示第 $i$ 幢楼房的宽度和高度。保证无重复的 $(W_i,H_i)$。
输出格式
输出所需最少的充气量。
说明/提示
#### 样例 1 解释
该方案只需 $20$ 个单位的充气量，为最少充气量：
#### 数据规模与约定
对于 $40$ 分的数据，$N \le 1000$。
对于 $100\%$ 的数据，$1 \le K \le N \le 10^6$，$1 \le W_i,H_i \le 10^6$。
#### 说明
**本题分值按 COCI 原题设置，满分 $90$。**
**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf) _T3 Kisik_。**