Auf Kunstausstellungen gibt es sehr häufig Stände, an denen Kinder ihre eigene Sandkunst gestalten können. Dazu füllt man normalerweise ein Glas oder eine Flasche mit Schichten verschiedenfarbigen Sandes. Dieses Jahr wird zum Dekorieren anstelle einer Flasche ein neuer Behälter verwendet! Dieser Behälter ist ein Glaskasten!

Der Kasten hat eine zweidimensionale rechteckige Vorderseite und ist genau 1 Einheit dick. Im Glaskasten werden $n-1$ senkrechte Trennwände angebracht, die ihn in $n$ Abschnitte unterteilen. Im folgenden Beispiel wird der Kasten mit 3 Trennwänden in 4 Abschnitte unterteilt:

Manchmal möchten die Kinder bestimmte Mengen jeder Farbe in jedem Abschnitt ihres Kunstwerks haben. Für jede Kombination aus Abschnitt und Sandfarbe geben sie eine Mindest- und eine Höchstmenge an. Deine Aufgabe ist es, ihnen zu helfen herauszufinden, wie ausgeglichen sie ihr Kunstwerk gestalten können. Dazu wird der Unterschied zwischen der Sandhöhe im Abschnitt mit dem höchsten gesamten Sandstand und der im Abschnitt mit dem niedrigsten gesamten Sandstand minimiert.

Eingabe

Jede Eingabe besteht aus einem einzigen Testfall. Beachte, dass dein Programm mit unterschiedlichen Eingaben mehrfach ausgeführt werden kann. Jede Eingabe beginnt mit einer Zeile mit 4 durch Leerzeichen getrennten ganzen Zahlen $n\ m\ w\ h$, wobei:

• $n$ ($2 \le n \le 200$) die Anzahl der Abschnitte ist;
• $m$ ($1 \le m \le 200$) die Anzahl der Sandfarben ist;
• $w,h$ ($1 \le w,h \le 5\,000$) die Breite und Höhe des Kastens sind (seine Tiefe beträgt immer 1).

Die nächste Zeile enthält $m$ durch Leerzeichen getrennte reelle Zahlen $v$ ($0<v \le w\cdot h$) mit höchstens 3 Nachkommastellen. Sie geben die Sandvolumina der einzelnen Farben an. Es muss nicht der gesamte Sand verwendet werden, aber die Mindestmengen für jeden Abschnitt müssen eingehalten werden.

Die nächste Zeile enthält $n-1$ durch Leerzeichen getrennte reelle Zahlen $x$ ($0<x<w$) mit höchstens 3 Nachkommastellen. Sie geben den Abstand jeder Trennwand von der linken Wand an. Die $x$ sind garantiert aufsteigend sortiert.

Jede der nächsten $n$ Zeilen enthält $m$ durch Leerzeichen getrennte reelle Zahlen $min$ ($0 \le min \le w\cdot h$) mit höchstens 3 Nachkommastellen. Das $j$-te Element der $i$-ten Zeile ist die Mindestmenge an Sand der Farbe $j$, die in Abschnitt $i$ gefüllt werden muss.

Jede der nächsten $n$ Zeilen enthält $m$ durch Leerzeichen getrennte reelle Zahlen $max$ ($0 \le max \le w\cdot h$) mit höchstens 3 Nachkommastellen. Das $j$-te Element der $i$-ten Zeile ist die Höchstmenge an Sand der Farbe $j$, die in Abschnitt $i$ gefüllt werden darf, und $min_{ij} \le max_{ij}$.

Ausgabe

Gib eine auf genau 3 Nachkommastellen gerundete reelle Zahl aus, die den kleinstmöglichen Unterschied zwischen der maximalen und der minimalen Sandhöhe der Abschnitte angibt. Es gibt immer eine Sandverteilung, die die Bedingungen der Eingabe erfüllt.

Beispiele

Eingabe 1

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

Ausgabe 1

0.750

Eingabe 2

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

Ausgabe 2

0.625

Eingabe 3

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

Ausgabe 3

0.266