[USACO19FEB] Painting the Barn G
题目描述
Farmer John 不太擅长多任务处理。他经常分心,很难完成一些长期的项目。目前,他正在谷仓的一侧刷油漆,但他一直忙着在很小的区域涂抹油漆,然后由于抚育母牛的需要而陷入困境,使谷仓的某些部分比其他部分涂有更多的油漆。
我们将谷仓的墙描述为一个 X-Y 平面,每次涂油漆的区域都是一个矩形。FJ 在这个平面上绘制了 $N$ 个矩形,每个矩形的边均与坐标轴平行。因此我们用矩形的左下角和右上角坐标来描述一个矩形。
FJ 想在谷仓里涂几层油漆,这样就不需要在不久的将来再次重新涂油漆。但是,他不想浪费时间涂过多的油漆。事实证明,$K$ 层涂料是最佳用量。但是因为涂油漆的面积太小了,FJ 并不太高兴。他决定最多再绘制两个**不相交**的矩形(这里的相交指两个矩形交的面积大于零,即如果两个矩形仅共用一条边或一个点,则不视为相交)来增加面积。当然不绘制新矩形或仅绘制一个新矩形也是允许的。
输入输出格式
输入格式
第一行两个整数 $N,K$($1 \leq N,K \leq 10^5$)。
接下来 $N$ 行,每行四个整数 $x_1,y_1,x_2,y_2$($0 \leq x_1,y_1,x_2,y_2 \leq 200$),描述一个矩形。其左下角坐标为 $(x_1,y_1)$,右上角坐标为 $x_2,y_2$。保证所有矩形面积为正,即其不会退化为线段或点。
和现有的矩形一样,新绘制的矩形,其左下角和右上角坐标也必须是整数,且坐标必须在 $0 \sim 200$ 之间,面积也必须为正。
输出格式
输出被涂油漆恰好 $K$ 次区域的最大面积。
输入输出样例
输入样例 #1
3 2
1 1 4 4
3 3 7 6
2 2 8 7
输出样例 #1
26