[Usaco2005 open]Lazy Cows

地母掌管着一片由 $2$ 行、$N$ 列方格组成的大地。大地上散落着 $M$ 处宝藏，每处宝藏占据一个方格，且任意两个宝藏不会位于同一个方格中。

为了防止宝藏被夺走，地母决定使用 $K$ 块矩形帆布覆盖所有宝藏。每块帆布必须覆盖一个由若干完整方格组成的矩形区域，其面积等于覆盖的方格数。

请你求出覆盖所有宝藏所需的 $K$ 块帆布的最小面积总和。

输入格式

第一行包含三个以空格分隔的整数 $M$、$K$ 和 $N$，分别表示宝藏数量、帆布数量和大地的列数。

接下来 $M$ 行，每行包含两个以空格分隔的整数，表示一处宝藏所在方格的行坐标和列坐标。

输出格式

输出一个整数，表示使用 $K$ 块矩形帆布覆盖所有宝藏所需的最小面积总和。

样例输入

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

样例输出

10

数据范围

• $1\le N\le 1.5\times 10^7$；
• $1\le M\le 1000$；
• $K\le M$；
• 每处宝藏的行坐标范围为 $1$ 至 $2$，列坐标范围为 $1$ 至 $N$；
• 任意两个宝藏不会位于同一个方格中。

来源与许可

本题为 USACO 2005 Open 试题「Lazy Cows」，题面与测试数据整理自 BZOJ。

样例 1

输入

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

输出

10