SP1672 GIWED - The Great Indian Wedding

在一个长宽为 $M \times N$ 的矩形公园里即将举行婚礼。公园的某些区域被 $K$ 块矩形地毯覆盖。这些地毯是 ItSucks 公司生产的，具有革命性的自清洁功能——它们能吸收所有接触到的液体！婚礼的组织者希望给公园浇水以保持草地的新鲜。假如没有地毯，组织者可以用一根水管轻松浇灌整个公园，但遗憾的是，水无法透过地毯渗透。组织者手上共有 $L$ 根水管可供使用，这些水管将被固定在组织者选定的位置，并不能移动。水从水管可以向四周扩散，直到碰到公园的边界或地毯为止。请计算在使用这 $L$ 根水管的情况下，能够浇灌的最大面积是多少。

第一行输入一个整数 $T$，表示共有多少个测试用例（$1 \le T \le 30$）。每个测试用例以一行开始，包含四个整数 $M, N, K, L$（$1 \le M \le 10000, 1 \le N \le 10000, 0 \le K \le 50, 1 \le L \le 10$）。接着有 $K$ 行，每行包含四个用空格分隔的整数 $x_1, y_1, x_2, y_2$，表示地毯左下角和右上角的坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$。假设 $x_1 < x_2$ 且 $y_1 < y_2$。地毯之间可能会相互覆盖。即便两块地毯在角落处相接，水也无法透过。

对于每个测试用例，输出一行，表示可以浇灌的最大面积。 **本翻译由 AI 自动生成**