Dans les expositions d'art, il est très courant de trouver des stands où les enfants peuvent créer leurs propres œuvres en sable. Cet art consiste généralement à remplir un bocal ou une bouteille de couches de sable de différentes couleurs. Cette année, un nouveau récipient remplace la bouteille pour la décoration ! Il s'agit d'une boîte en verre !

La boîte a une face rectangulaire en deux dimensions et une épaisseur d'exactement 1 unité. À l'intérieur, $n-1$ cloisons verticales la séparent en $n$ compartiments. Dans l'exemple ci-dessous, 3 cloisons divisent la boîte en 4 compartiments :

Les enfants souhaitent parfois certaines quantités de chaque couleur dans chaque compartiment de leur œuvre. Ils indiquent un minimum et un maximum pour chaque combinaison de compartiment et de couleur de sable. Votre tâche consiste à les aider à déterminer à quel point ils peuvent équilibrer leur œuvre. Pour cela, il faut minimiser la différence de hauteur de sable entre le compartiment dont le niveau total de sable est le plus haut et celui dont le niveau total est le plus bas.

Entrée

Chaque entrée contient un seul cas de test. Notez que votre programme peut être exécuté plusieurs fois sur des entrées différentes. Chaque entrée commence par une ligne contenant 4 entiers séparés par des espaces, $n\ m\ w\ h$, où :

• $n$ ($2 \le n \le 200$) est le nombre de compartiments ;
• $m$ ($1 \le m \le 200$) est le nombre de couleurs de sable ;
• $w,h$ ($1 \le w,h \le 5\,000$) sont la largeur et la hauteur de la boîte (sa profondeur vaut toujours 1).

La ligne suivante contient $m$ nombres réels $v$ ($0<v \le w\cdot h$), séparés par des espaces et comportant au plus 3 chiffres après la virgule, représentant les volumes de chaque couleur de sable. Il n'est pas nécessaire d'utiliser tout le sable, mais les minimums de chaque compartiment doivent être respectés.

La ligne suivante contient $n-1$ nombres réels $x$ ($0<x<w$), séparés par des espaces et comportant au plus 3 chiffres après la virgule, représentant la distance de chaque cloison à la paroi gauche. Les $x$ sont garantis triés par ordre croissant.

Chacune des $n$ lignes suivantes contient $m$ nombres réels $min$ ($0 \le min \le w\cdot h$), séparés par des espaces et comportant au plus 3 chiffres après la virgule. Le $j$-ième élément de la $i$-ième ligne est la quantité minimale de sable de couleur $j$ à placer dans le compartiment $i$.

Chacune des $n$ lignes suivantes contient $m$ nombres réels $max$ ($0 \le max \le w\cdot h$), séparés par des espaces et comportant au plus 3 chiffres après la virgule. Le $j$-ième élément de la $i$-ième ligne est la quantité maximale de sable de couleur $j$ à placer dans le compartiment $i$, et $min_{ij} \le max_{ij}$.

Sortie

Affichez un nombre réel arrondi à exactement 3 chiffres après la virgule, représentant la plus petite différence possible entre la hauteur maximale et la hauteur minimale du sable dans les compartiments. Il existe toujours une répartition du sable respectant les contraintes de l'entrée.

Exemples

Entrée 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

Sortie 1

0.750

Entrée 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

Sortie 2

0.625

Entrée 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

Sortie 3

0.266