בתערוכות אמנות נפוצים מאוד דוכנים שבהם ילדים יכולים ליצור אמנות חול משלהם. בדרך כלל יוצרים אמנות זו באמצעות מילוי צנצנת או בקבוק בשכבות של חול בצבעים שונים. השנה משתמשים בכלי חדש לקישוט במקום בקבוק! הכלי הוא קופסת זכוכית!

לקופסה חזית מלבנית דו־ממדית ועובי של יחידה אחת בדיוק. בתוך קופסת הזכוכית מציבים $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).

השורה הבאה מכילה $m$ מספרים ממשיים $v$ ($0<v \le w\cdot h$), המופרדים ברווחים ובעלי לכל היותר 3 ספרות אחרי הנקודה העשרונית, המייצגים את נפחי החול מכל צבע. אין צורך להשתמש בכל החול, אך יש לעמוד בכמויות המזעריות לכל תא.

השורה הבאה מכילה $n-1$ מספרים ממשיים $x$ ($0<x<w$), המופרדים ברווחים ובעלי לכל היותר 3 ספרות אחרי הנקודה העשרונית, המייצגים את המרחק של כל מחיצה מהדופן השמאלית. מובטח שערכי $x$ ממוינים בסדר עולה.

כל אחת מ־$n$ השורות הבאות מכילה $m$ מספרים ממשיים $min$ ($0 \le min \le w\cdot h$), המופרדים ברווחים ובעלי לכל היותר 3 ספרות אחרי הנקודה העשרונית. האיבר ה־$j$ בשורה ה־$i$ הוא הכמות המזערית של חול בצבע $j$ שיש להכניס לתא $i$.

כל אחת מ־$n$ השורות הבאות מכילה $m$ מספרים ממשיים $max$ ($0 \le max \le w\cdot h$), המופרדים ברווחים ובעלי לכל היותר 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