1232 - 矩形覆盖

在平面上有n个点(n<=50),每个点用一对整数坐标表示。例如:当n=4时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。

这些点可以用k个矩形(1&lt;=k&lt;=4)全部覆盖,矩形的边平行于坐标轴。当k=2时,可用如图二的两个矩形s1<span style="line-height:1.5;">,s2覆盖,s1,s2面积和为4。问题是当n个点坐标和k给出后,怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。</span><span style="line-height:1.5;"></span> 

<span style="line-height:1.5;"><br />

输入

每个测试文件只包含一组测试数据,每组输入的第一行输入两个整数n和k(n<=50,1<=k<=4)。

接下来n行,每行输入两个整数x和y(0<=x,y<=500),表示一个点的坐标。


输出

对于每组输入数据,输出一个整数,即满足条件的最小的矩形面积之和。


样例

输入

4 2
1 1
2 2
3 6
0 7

输出

4

来源

NOIP全国联赛提高组 2002年NOIP全国联赛提高组

时间限制 1 秒
内存限制 125 MB
讨论 统计
上一题 下一题