모래 그림

공예 축제 부스에서 아이들이 모래 그림을 만든다. 보통은 병에 색이 다른 모래를 층층이 채우지만, 올해는 유리 상자를 쓴다.

상자는 정면에서 보면 직사각형이고 두께는 정확히 1이다. 그래서 어떤 영역에 담기는 모래의 부피는 정면에서 본 그 영역의 넓이와 같다. 상자 안에는 세로 칸막이 $n-1$개가 서 있어서 내부가 $n$개 구역으로 나뉜다. 아래 그림은 칸막이 3개로 4개 구역을 만든 상자다.

아이들은 구역마다, 색마다 넣을 모래의 최솟값과 최댓값을 정해 준다. 모래는 한 구역 안에서 평평하게 쌓이므로, 구역의 모래 높이는 그 구역에 담긴 모래의 부피를 구역의 폭으로 나눈 값이다. 작품을 최대한 고르게 만들어라. 즉 모래가 가장 높은 구역과 가장 낮은 구역의 높이 차이를 가장 작게 하라.

첫째 줄에 정수 $n$, $m$, $w$, $h$가 공백으로 구분되어 주어진다.

• $n$ ($2 \le n \le 200$)은 구역의 개수다.
• $m$ ($1 \le m \le 200$)은 모래 색의 개수다.
• $w$와 $h$ ($1 \le w, h \le 5000$)는 상자의 폭과 높이다. 두께는 항상 1이다.

둘째 줄에 소수점 아래 세 자리까지인 실수 $m$개 $v$ ($0 < v \le w \times h$)가 주어진다. $j$번째 값은 $j$번 색 모래의 부피다. 모래를 전부 쓸 필요는 없지만, 각 구역의 최솟값은 반드시 채워야 한다.

셋째 줄에 소수점 아래 세 자리까지인 실수 $n-1$개 $x$ ($0 < x < w$)가 증가하는 순서로 주어진다. 각 값은 왼쪽 벽에서 칸막이까지의 거리다.

다음 $n$개 줄에는 각각 소수점 아래 세 자리까지인 실수 $m$개 $\min$ ($0 \le \min \le w \times h$)이 주어진다. $i$번째 줄의 $j$번째 값은 구역 $i$에 넣을 색 $j$ 모래의 최솟값이다.

그다음 $n$개 줄에는 각각 소수점 아래 세 자리까지인 실수 $m$개 $\max$ ($0 \le \max \le w \times h$)가 주어진다. $i$번째 줄의 $j$번째 값은 구역 $i$에 넣을 색 $j$ 모래의 최댓값이고, $\min_{ij} \le \max_{ij}$다.

모래가 가장 높은 구역과 가장 낮은 구역의 높이 차이의 최솟값을 소수점 아래 정확히 세 자리로 반올림해 한 줄에 출력한다. 입력의 조건을 모두 만족하는 분배 방법은 항상 존재한다.