ג'ייס משחק במשחק של ARAM: Mayhem. הוא הגיע לשלב בחירת התוספים (Augments) ומחפש את התוסף המושלם שיוביל את הקבוצה שלו לניצחון.ליתר דיוק, הוא מחפש בנואשות אחר תוסף הזהב הידוע בשם Slow and Steady.
ממשק המשחק לבחירת קלפים. אופס, נראה שג'ייס לא יוכל למצוא את Slow and Steady במאגר הפריזמטי...
כעת, ממשק המשחק מציג לג'ייס $k$ קלפי תוספים. אמנם לכל קלף יש השפעה שונה, אך עבור ג'ייס, הקלף הגלוי ה-$i$ שווה $a_i$ נקודות ערך. בחפיסה ממתין מאגר נסתר של $n$ קלפי תוספים אחרים. ידוע שנקודות הערך של קלפים אלה מהוות את ריבוי-הקבוצות (multiset) $\{b_1, b_2, \dots, b_n\}$, אך סדרם מעורבב באקראי בהתפלגות אחידה.
ג'ייס יכול לרענן כל אחד מ-$k$ חריצי הקלפים לכל היותר פעם אחת. התהליך פועל כך:
- מתחת לכל אחד מ-$k$ הקלפים ישנם כפתורי הגרלה מחדש (reroll) נפרדים (כפי שמוצג בממשק המשחק).
- ג'ייס יכול לבחור חריץ שעדיין לא הוגרל מחדש, להשליך את הקלף הנוכחי ולשלוף את הקלף העליון מהחפיסה כדי להחליפו.
- ג'ייס רואה את תוצאת ההגרלה מחדש מיד לפני שהוא מחליט על המהלך הבא שלו: האם להגריל מחדש חריץ זמין אחר, או לעצור.
בסוף התהליך, ג'ייס יבחר קלף אחד מתוך $k$ הקלפים הגלויים באותו רגע על המסך.
ג'ייס משחק באופן אופטימלי כדי למקסם את תוחלת הערך של הקלף שיבחר לבסוף. חשבו את רמת העוצמה הצפויה המרבית הזו.
קלט
השורה הראשונה מכילה שני מספרים שלמים $k$ ו-$n$ ($1 \le k \le n \le 10^5$), המציינים את מספר החריצים הגלויים ואת מספר הקלפים בחפיסה.
השורה השנייה מכילה $k$ מספרים שלמים $a_1, a_2, \dots, a_k$ ($-10^5 \le a_i \le 10^5$), המציינים את רמות העוצמה של הקלפים הגלויים בתחילה.
השורה השלישית מכילה $n$ מספרים שלמים $b_1, b_2, \dots, b_n$ ($-10^5 \le b_i \le 10^5$), המציינים את רמות העוצמה של הקלפים בחפיסה.
פלט
הדפיסו את תוחלת הערך המרבית של הקלף כמספר ממשי עשרוני יחיד.
תשובתכם תיחשב נכונה אם השגיאה המוחלטת או היחסית שלה אינה עולה על $10^{-4}$. באופן פורמלי, נניח שהפלט שלכם הוא $a$ ותשובת השופטים היא $b$; הפלט שלכם יתקבל אם ורק אם $\frac{|a - b|}{\max(1, |b|)} \le 10^{-4}$.
דוגמאות
קלט 1
1 2 10 1 100
פלט 1
50.5
קלט 2
3 5 3 4 7 1 2 3 5 8
פלט 2
7.4
קלט 3
2 4 -1 -2 -3 -4 -5 -6
פלט 3
-1
קלט 4
5 14 1 3 5 7 9 -1 -1 0 0 2 2 4 4 6 6 8 8 10 10
פלט 4
9.505494505