Tại các triển lãm nghệ thuật, rất thường có những gian hàng để trẻ em tự tạo ra tác phẩm nghệ thuật bằng cát của riêng mình. Loại tác phẩm này thường được làm bằng cách đổ các lớp cát có màu khác nhau vào một chiếc lọ hoặc chai. Năm nay, một loại vật chứa mới được dùng để trang trí thay cho chai! Đó là một chiếc hộp kính!

Hộp có mặt trước là một hình chữ nhật hai chiều và độ dày đúng 1 đơn vị. Bên trong hộp kính, người ta đặt $n-1$ vách ngăn thẳng đứng để chia hộp thành $n$ ngăn. Trong ví dụ dưới đây, hộp được chia thành 4 ngăn bằng 3 vách ngăn:

Đôi khi trẻ em muốn có một lượng nhất định của mỗi màu trong từng ngăn của tác phẩm. Các em chỉ định lượng tối thiểu và tối đa cho mỗi cặp gồm ngăn và màu cát. Nhiệm vụ của bạn là giúp các em tìm xem tác phẩm có thể cân bằng đến mức nào. Điều này được thực hiện bằng cách tối thiểu hóa chênh lệch chiều cao cát giữa ngăn có mức cát tổng thể cao nhất và ngăn có mức cát tổng thể thấp nhất.

Dữ liệu vào

Mỗi dữ liệu vào gồm một bộ kiểm thử duy nhất. Lưu ý rằng chương trình của bạn có thể được chạy nhiều lần với các dữ liệu vào khác nhau. Mỗi dữ liệu vào bắt đầu bằng một dòng gồm 4 số nguyên cách nhau bởi dấu cách, $n\ m\ w\ h$, trong đó:

• $n$ ($2 \le n \le 200$) là số ngăn.
• $m$ ($1 \le m \le 200$) là số màu cát.
• $w,h$ ($1 \le w,h \le 5\,000$) là chiều rộng và chiều cao của hộp (chiều sâu luôn bằng 1).

Dòng tiếp theo chứa $m$ số thực $v$ ($0<v \le w\cdot h$), cách nhau bởi dấu cách và có nhiều nhất 3 chữ số sau dấu thập phân, biểu diễn thể tích cát của mỗi màu. Không cần dùng hết cát, nhưng phải thỏa mãn lượng tối thiểu của từng ngăn.

Dòng tiếp theo chứa $n-1$ số thực $x$ ($0<x<w$), cách nhau bởi dấu cách và có nhiều nhất 3 chữ số sau dấu thập phân, biểu diễn khoảng cách từ mỗi vách ngăn đến thành bên trái. Các giá trị $x$ được đảm bảo đã sắp xếp theo thứ tự tăng dần.

Mỗi dòng trong $n$ dòng tiếp theo chứa $m$ số thực $min$ ($0 \le min \le w\cdot h$), cách nhau bởi dấu cách và có nhiều nhất 3 chữ số sau dấu thập phân. Phần tử thứ $j$ của dòng thứ $i$ là lượng tối thiểu cát màu $j$ phải được đặt vào ngăn $i$.

Mỗi dòng trong $n$ dòng tiếp theo chứa $m$ số thực $max$ ($0 \le max \le w\cdot h$), cách nhau bởi dấu cách và có nhiều nhất 3 chữ số sau dấu thập phân. Phần tử thứ $j$ của dòng thứ $i$ là lượng tối đa cát màu $j$ được đặt vào ngăn $i$, và $min_{ij} \le max_{ij}$.

Dữ liệu ra

In ra một số thực được làm tròn đến đúng 3 chữ số sau dấu thập phân, biểu diễn chênh lệch nhỏ nhất có thể giữa chiều cao cát lớn nhất và nhỏ nhất trong các ngăn. Luôn tồn tại một cách phân bố cát thỏa mãn các ràng buộc trong dữ liệu vào.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

0.750

Dữ liệu vào 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

Dữ liệu ra 2

0.625

Dữ liệu vào 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

Dữ liệu ra 3

0.266