Nas exposições de arte, é muito comum haver bancas onde as crianças podem criar a sua própria arte com areia. Normalmente, esta arte é feita enchendo um frasco ou uma garrafa com camadas de areia de cores diferentes. Este ano, em vez de uma garrafa, é usado um novo recipiente para decorar! O recipiente é uma caixa de vidro!

A caixa tem uma face retangular bidimensional e uma espessura de exatamente 1 unidade. No seu interior, são colocadas $n-1$ divisórias verticais que a separam em $n$ secções. No exemplo abaixo, 3 divisórias dividem a caixa em 4 secções:

Por vezes, as crianças querem determinadas quantidades de cada cor em cada secção da sua obra. Especificam um mínimo e um máximo para cada combinação de secção e cor de areia. A sua tarefa é ajudá-las a determinar quão equilibrada pode ficar a obra. Para isso, deve minimizar a diferença entre a altura da areia na secção com o nível total de areia mais alto e na secção com o nível total mais baixo.

Entrada

Cada entrada contém um único caso de teste. Note que o seu programa pode ser executado várias vezes com entradas diferentes. Cada entrada começa com uma linha com 4 inteiros separados por espaços, $n\ m\ w\ h$, onde:

• $n$ ($2 \le n \le 200$) é o número de secções.
• $m$ ($1 \le m \le 200$) é o número de cores de areia.
• $w,h$ ($1 \le w,h \le 5\,000$) são a largura e a altura da caixa (a profundidade é sempre 1).

A linha seguinte contém $m$ números reais $v$ ($0<v \le w\cdot h$), separados por espaços e com no máximo 3 casas decimais, que representam os volumes de areia de cada cor. Não é necessário utilizar toda a areia, mas os mínimos de cada secção devem ser respeitados.

A linha seguinte contém $n-1$ números reais $x$ ($0<x<w$), separados por espaços e com no máximo 3 casas decimais, que representam a distância de cada divisória à parede esquerda. É garantido que os valores $x$ estão ordenados por ordem crescente.

Cada uma das $n$ linhas seguintes contém $m$ números reais $min$ ($0 \le min \le w\cdot h$), separados por espaços e com no máximo 3 casas decimais. O elemento $j$ da linha $i$ é a quantidade mínima de areia da cor $j$ a colocar na secção $i$.

Cada uma das $n$ linhas seguintes contém $m$ números reais $max$ ($0 \le max \le w\cdot h$), separados por espaços e com no máximo 3 casas decimais. O elemento $j$ da linha $i$ é a quantidade máxima de areia da cor $j$ a colocar na secção $i$, e $min_{ij} \le max_{ij}$.

Saída

Imprima um número real arredondado para exatamente 3 casas decimais que represente a menor diferença possível entre as alturas máxima e mínima de areia nas secções. Existirá sempre uma distribuição de areia que satisfaça as restrições da entrada.

Exemplos

Entrada 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

Saída 1

0.750

Entrada 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

Saída 2

0.625

Entrada 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

Saída 3

0.266