Sand Art

A booth at a craft fair lets children make sand art. The usual container is a bottle packed with layers of colored sand. This year the container is a glass box.

Seen from the front the box is a rectangle, and its thickness is exactly 1, so the volume of sand in a region equals the area of that region on the front face. Inside the box, $n-1$ vertical dividers split the interior into $n$ sections. The picture below shows a box split into 4 sections by 3 dividers.

For every section and every color, a child gives the smallest and the largest amount of that color the section may hold. Sand settles flat inside a section, so the height of a section is the volume of sand in it divided by the width of the section. Make the artwork as even as possible: minimize the difference between the height of the tallest section and the height of the shortest section.

The first line holds the integers $n$, $m$, $w$, $h$, separated by spaces.

• $n$ ($2 \le n \le 200$) is the number of sections.
• $m$ ($1 \le m \le 200$) is the number of sand colors.
• $w$ and $h$ ($1 \le w, h \le 5000$) are the width and the height of the box. Its thickness is always 1.

The second line holds $m$ real numbers $v$ ($0 < v \le w \times h$) with at most 3 decimal places. The $j$th value is the volume of sand color $j$. You do not have to use all of the sand, but every section minimum must be met.

The third line holds $n-1$ real numbers $x$ ($0 < x < w$) with at most 3 decimal places, in increasing order. Each value is the distance from the left wall to a divider.

Each of the next $n$ lines holds $m$ real numbers $\min$ ($0 \le \min \le w \times h$) with at most 3 decimal places. The $j$th value on the $i$th line is the smallest amount of sand color $j$ to put in section $i$.

Each of the next $n$ lines holds $m$ real numbers $\max$ ($0 \le \max \le w \times h$) with at most 3 decimal places. The $j$th value on the $i$th line is the largest amount of sand color $j$ to put in section $i$, and $\min_{ij} \le \max_{ij}$.

Print, on one line, the smallest possible difference between the tallest and the shortest section height, rounded to exactly 3 digits after the decimal point. A distribution that satisfies every constraint in the input always exists.