题目描述

农夫约翰不擅长多任务处理。他经常分心，很难完成长的项目。目前，他正试图在谷仓的一侧上漆，但他一直在画小矩形区域，然后由于照料奶牛的需要而偏离了方向，使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维 $x$-$y$ 平面，农夫约翰在该平面上绘制 $n$ 个矩形，每个矩形的边都与坐标轴平行，每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆，这样在不久的将来就不需要再重新粉刷了。但是，他不想浪费时间涂太多的油漆。结果表明，$K$ 涂层是最佳用量。请在他画完所有的长方形后，帮他确定谷仓有多少面积被 $K$ 层油漆覆盖。

输入格式

第一行包含两个整数 $n$ 和 $K$，分别表示矩形的数量和目标涂层数。

接下来 $n$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，描述一个正在绘制的矩形区域，左下角为 $(x_1, y_1)$，右上角为 $(x_2, y_2)$。所有 $x$ 和 $y$ 值都在 $0$ 到 $1000$ 范围内，并且所有矩形都有正面积。

输出格式

输出一个整数，表示谷仓被恰好 $K$ 层油漆覆盖的面积。

样例

3 2
1 1 5 5
4 4 7 6
3 3 8 7

8

数据范围与提示

• $1 \le K \le n \le 10^5$
• $0 \le x_1, y_1, x_2, y_2 \le 1000$

来源

CSPJ-重点算法班