题目描述

农夫 John 对给牧场使用了高效肥料感到后悔。因为草长得太快，以至于奶牛们吃草时甚至不再走动。奶牛们变得又胖又懒……冬天就要来了。

为了给奶牛提供庇护，John 决定在奶牛当前位置上方建造牛棚。因为奶牛太懒，它们不会走进牛棚，所以牛棚必须完全覆盖它们的位置。

牧场是一块大小为 $2 \times B$ 的矩形区域（$1 \leq B \leq 15{,}000{,}000$），其中一些格子中有奶牛，其余为空地。总共有 $N$ 头奶牛（$1 \leq N \leq 1000$）被放置在不同的格子中（没有两个奶牛在同一个格子中）。

现在 John 想要建造 $K$ 个长方形牛棚（$1 \leq K \leq N$），每个牛棚必须是 横平竖直的矩形区域，并且必须：

完全覆盖所有奶牛的位置

牛棚之间不能重叠

使所有牛棚的总面积最小

输入格式

第 1 行输入三个整数：$N,\ K,\ B$

$N$：奶牛的数量

$K$：牛棚的数量

$B$：牧场的列数（2 行 $B$ 列）

接下来的 $N$ 行，每行两个整数 $r_i,\ c_i\ (1 \leq r_i \leq 2,\ 1 \leq c_i \leq B)$ 表示第 $i$ 头奶牛的位置

输出格式

输出一个整数，表示用 $K$ 个牛棚覆盖所有奶牛的最小总面积

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

10