沙画 - 問題

在艺术展览中，经常会有摊位让孩子们创作属于自己的沙画。这种艺术品通常是通过取一个罐子或瓶子，并分层填充不同颜色的沙子来制作的。今年，我们不再使用瓶子，而是使用一种新的容器进行装饰！这个容器是一个玻璃盒！

这个盒子有一个二维矩形面，厚度正好为 1 个单位。在玻璃盒内，放置了 $n-1$ 个垂直隔板，将其分隔成 $n$ 个部分。在下方的示例中，盒子使用 3 个隔板被分成了 4 个部分：

有时，孩子们希望在他们的艺术品中，每个部分都有特定数量的每种颜色的沙子。他们为每个“部分-沙子颜色”组合指定了最小值和最大值。你的任务是帮助他们找出如何使艺术品尽可能平衡。这可以通过最小化沙子高度最高的区域与沙子高度最低的区域之间的差值来实现。

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个输入以一行包含 4 个空格分隔的整数 $n, m, w, h$ 开始，其中：

下一行将包含 $m$ 个空格分隔的实数（最多 3 位小数）$v$ ($0 < v \le w \cdot h$)，代表每种颜色沙子的总量。不一定要用完所有的沙子，但必须满足每个部分的最小值要求。

下一行将包含 $n-1$ 个空格分隔的实数（最多 3 位小数）$x$ ($0 < x < w$)，代表每个隔板距离左侧墙壁的距离。保证 $x$ 是按升序排列的。

接下来的 $n$ 行，每行包含 $m$ 个空格分隔的实数（最多 3 位小数）$min$ ($0 \le min \le w \cdot h$)。第 $i$ 行的第 $j$ 个元素是放入第 $i$ 个部分中沙子颜色 $j$ 的最小量。

接下来的 $n$ 行，每行包含 $m$ 个空格分隔的实数（最多 3 位小数）$max$ ($0 \le max \le w \cdot h$)。第 $i$ 行的第 $j$ 个元素是放入第 $i$ 个部分中沙子颜色 $j$ 的最大量，且满足 $min_{ij} \le max_{ij}$。

输出一个四舍五入到小数点后正好 3 位的实数，表示各部分中沙子最高高度与最低高度之间可能达到的最小差值。题目保证一定存在满足输入约束的沙子分配方案。

2 2 5 5
2.0 2.0
4.0
1.0 0.0
0.0 1.0
1.0 0.0
0.0 2.0

0.750

2 2 5 5
2.0 2.0
4.0
1.0 0.0
0.0 1.0
1.5 0.0
0.0 2.0

0.625

2 5 11 10
3.0 4.0 4.0 9.0 2.0
4.0
2.0 2.0 1.0 0.5 0.25
0.0 2.0 0.0 4.0 1.0
2.0 2.0 3.0 4.0 0.75
0.0 2.1 0.0 5.1 1.1

0.266

QOJ.ac