沙畫 - Problème

在藝術展覽中，常常會設置攤位，讓孩子製作屬於自己的沙畫。這種藝術通常是拿一個罐子或瓶子，將不同顏色的沙子一層層裝入其中。今年不用瓶子，而是用一種新的容器來裝飾！這個容器是一個玻璃盒！

盒子的正面是二維矩形，厚度恰好為 1 單位。在玻璃盒內放置 $n-1$ 塊垂直隔板，將盒子分成 $n$ 個區域。在下面的例子中，用 3 塊隔板將盒子分成了 4 個區域：

有時，孩子希望作品的每個區域中，各種顏色的沙子都具有一定的用量。他們為每一組區域與沙子顏色指定最小用量和最大用量。你的任務是幫他們找出作品能做到多麼平衡。做法是將沙子總高度最高的區域與沙子總高度最低的區域之間的高度差最小化。

每份輸入只包含一筆測試資料。請注意，你的程式可能會針對不同輸入執行多次。每份輸入的第一行包含 4 個以空白分隔的整數 $n\ m\ w\ h$，其中：

下一行包含 $m$ 個以空白分隔的實數 $v$（$0<v \le w\cdot h$），各數最多有 3 位小數，表示每種顏色沙子的體積。不必用完所有沙子，但必須滿足每個區域的最小用量要求。

下一行包含 $n-1$ 個以空白分隔的實數 $x$（$0<x<w$），各數最多有 3 位小數，表示每塊隔板到左側壁的距離。保證這些 $x$ 按遞增順序排列。

接下來 $n$ 行，每行包含 $m$ 個以空白分隔的實數 $min$（$0 \le min \le w\cdot h$），各數最多有 3 位小數。第 $i$ 行的第 $j$ 個數表示在區域 $i$ 中必須放入的顏色 $j$ 的沙子的最小用量。

接下來 $n$ 行，每行包含 $m$ 個以空白分隔的實數 $max$（$0 \le max \le w\cdot h$），各數最多有 3 位小數。第 $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