星际国家殖民联盟（CAIN）决定在火星上为 $K$ 个家庭建造一个城镇。因此，需要建造总共 $K$ 栋建筑物，每个家庭一栋。对于每个家庭，将从宇宙中最好的建筑师准备的 $N$ 种不同的建筑物设计中选择一种。所有建筑物均为矩形，第 $i$ 栋建筑物宽为 $W_i$ 单位，高为 $H_i$ 单位。此外，由于 CAIN 提倡多样性，所有家庭都将获得不同的设计。

建筑物并排建造，使得它们的底部位于同一条水平线上。建造完成后，城市需要充满空气，因此城市将被一堵巨大的玻璃墙封闭，以将空气保持在内部。玻璃墙也将呈矩形，其各边与建筑物的各边平行。

由于在火星上维持空气的成本很高，你的任务是在所有可能的选择中，选出一种方案，使得所需的空气量最少（每单位面积需要一个单位的空气）。

第一个样例中一种可能的城市规划，仅需要 20 个单位的空气。我们选择不建造宽度为 3 的那栋建筑物。

输入格式

第一行包含两个整数 $N$ 和 $K$，含义如题面所述（$1 \le K \le N \le 1\,000\,000$）。

接下来的 $N$ 行，每行包含两个整数 $W_i$ 和 $H_i$，表示第 $i$ 栋建筑物的宽度和高度（$1 \le W_i, H_i \le 1\,000\,000$）。所有的二元组 $(W_i, H_i)$ 互不相同。

输出格式

在第一行输出所需的最小空气量。

数据范围

在总分值为 40 分的测试数据中，$N \le 1\,000$。

样例

输入样例 1

4 3
2 3
2 2
1 4
3 2

输出样例 1

20

输入样例 2

3 3
1 1
3 3
2 2

输出样例 2

18

输入样例 3

4 1
6 4
4 5
19 1
3 6

输出样例 3

18