ในงานแสดงศิลปะ มักมีบูธที่เด็ก ๆ สามารถสร้างงานศิลปะจากทรายของตนเองได้ งานชนิดนี้มักทำโดยนำโหลหรือขวดมาใส่ทรายสีต่าง ๆ ซ้อนกันเป็นชั้น ๆ ปีนี้จะใช้ภาชนะชนิดใหม่สำหรับตกแต่งแทนขวด! ภาชนะนั้นคือกล่องแก้ว!

ด้านหน้าของกล่องเป็นรูปสี่เหลี่ยมผืนผ้าสองมิติ และกล่องมีความหนาเท่ากับ 1 หน่วยพอดี ภายในกล่องแก้วมีแผ่นกั้นแนวตั้ง $n-1$ แผ่น แบ่งกล่องออกเป็น $n$ ช่อง ในตัวอย่างด้านล่าง กล่องถูกแบ่งเป็น 4 ช่องด้วยแผ่นกั้น 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 5\,000$) คือความกว้างและความสูงของกล่อง (ความลึกเท่ากับ 1 เสมอ)

บรรทัดถัดไปมีจำนวนจริง $v$ ($0<v \le w\cdot h$) จำนวน $m$ จำนวนคั่นด้วยช่องว่าง แต่ละจำนวนมีทศนิยมไม่เกิน 3 ตำแหน่ง แทนปริมาตรทรายแต่ละสี ไม่จำเป็นต้องใช้ทรายทั้งหมด แต่ต้องเป็นไปตามปริมาณต่ำสุดที่กำหนดสำหรับแต่ละช่อง

บรรทัดถัดไปมีจำนวนจริง $x$ ($0<x<w$) จำนวน $n-1$ จำนวนคั่นด้วยช่องว่าง แต่ละจำนวนมีทศนิยมไม่เกิน 3 ตำแหน่ง แทนระยะจากผนังด้านซ้ายถึงแผ่นกั้นแต่ละแผ่น รับประกันว่าค่า $x$ เรียงจากน้อยไปมาก

แต่ละบรรทัดใน $n$ บรรทัดถัดไปมีจำนวนจริง $min$ ($0 \le min \le w\cdot h$) จำนวน $m$ จำนวนคั่นด้วยช่องว่าง แต่ละจำนวนมีทศนิยมไม่เกิน 3 ตำแหน่ง สมาชิกที่ $j$ ของแถวที่ $i$ คือปริมาณต่ำสุดของทรายสี $j$ ที่ต้องใส่ในช่อง $i$

แต่ละบรรทัดใน $n$ บรรทัดถัดไปมีจำนวนจริง $max$ ($0 \le max \le w\cdot h$) จำนวน $m$ จำนวนคั่นด้วยช่องว่าง แต่ละจำนวนมีทศนิยมไม่เกิน 3 ตำแหน่ง สมาชิกที่ $j$ ของแถวที่ $i$ คือปริมาณสูงสุดของทรายสี $j$ ที่ใส่ในช่อง $i$ ได้ และ $min_{ij} \le max_{ij}$

ข้อมูลส่งออก

แสดงจำนวนจริงที่ปัดเศษให้มีทศนิยม 3 ตำแหน่งพอดี แทนผลต่างน้อยที่สุดที่เป็นไปได้ระหว่างความสูงทรายสูงสุดและต่ำสุดในช่องต่าง ๆ จะมีวิธีแบ่งทรายที่เป็นไปตามข้อกำหนดในข้อมูลนำเข้าเสมอ

ตัวอย่าง

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 1

0.750

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 2

0.625

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 3

0.266