题目描述

CAIN 组织决定为 $K$ 个家庭在火星上建立一个新的小镇，因此将建立 $K$ 幢楼房，每家一幢。CAIN 提供了 $N$ 种不同的楼房设计，需要从中选出 $K$ 种不同的设计，每种被选中的设计建造一幢楼房。每种设计只能选用一次。

楼房都互相紧挨着，也就是说它们在同一直线上。在建设之后，城市需要进行充气，并被保存在一个玻璃墙内。玻璃墙只能围住一片矩形区域，因此充气的范围也是一个矩形区域。

求出所需最少的充气量。

输入格式

从文件 building.in 中读入数据。

第一行输入整数 $N,K$。

接下来的 $N$ 行，每行输入整数 $W_i,H_i$，表示第 $i$ 种设计的楼房宽度和高度。保证无重复的 $(W_i,H_i)$。

输出格式

将答案输出到文件 building.out 中。

输出所需最少的充气量。

样例

4 3
2 3
2 2
1 4
3 2

20

3 3
1 1
3 3
2 2

18

4 1
6 4
4 5
19 1
3 6

18

样例解释

样例 1

该方案只需 $20$ 个单位的充气量，为最少充气量：

数据范围

对于 $40$ 分的数据，$N \le 1000$。

对于 $100\%$ 的数据，$1 \le K \le N \le 10^6$，$1 \le W_i,H_i \le 10^6$。