Jayce está jugando una partida de ARAM: Mayhem. Ha llegado a la fase de Selección de Aumentos y está buscando el aumento perfecto para carrilear a su equipo. Específicamente, está buscando desesperadamente el aumento Dorado conocido como Slow and Steady.
La interfaz del juego para la selección de cartas. Vaya, parece que Jayce no puede encontrar Slow and Steady en el grupo Prismático...
Actualmente, la interfaz del juego le presenta $k$ cartas de aumento a Jayce. Aunque cada carta tiene un efecto diferente, para Jayce, la $i$-ésima carta visible vale $a_i$ puntos de valor. Hay una reserva oculta de otras $n$ cartas de aumento esperando en el mazo. Se sabe que los puntos de valor de estas cartas son el multiconjunto $\{b_1, b_2, \dots, b_n\}$, pero su orden se baraja de manera uniforme al azar.
Jayce puede actualizar cada una de las $k$ ranuras de cartas como máximo una vez. El proceso funciona de la siguiente manera:
- Hay botones individuales de cambio (reroll) debajo de cada una de las $k$ cartas (como se muestra en la interfaz del juego).
- Jayce puede elegir una ranura que aún no haya sido cambiada, descartar la carta actual y robar la carta superior del mazo para reemplazarla.
- Jayce ve el resultado de un cambio inmediatamente antes de decidir su siguiente movimiento: si cambiar otra ranura disponible o detenerse.
Al final del proceso, Jayce seleccionará una carta entre las $k$ cartas visiblemente actuales en la pantalla.
Jayce juega de manera óptima para maximizar el valor esperado de la carta que finalmente elija. Calcula este nivel de poder esperado máximo.
Entrada
La primera línea contiene dos enteros $k$ y $n$ ($1 \le k \le n \le 10^5$), que indican el número de ranuras visibles y el número de cartas en el mazo.
La segunda línea contiene $k$ enteros $a_1, a_2, \dots, a_k$ ($-10^5 \le a_i \le 10^5$), que indican los niveles de poder de las cartas inicialmente visibles.
La tercera línea contiene $n$ enteros $b_1, b_2, \dots, b_n$ ($-10^5 \le b_i \le 10^5$), que indican los niveles de poder de las cartas en el mazo.
Salida
Imprime el valor esperado máximo de la carta como un único número real decimal.
Tu respuesta se considerará correcta si su error absoluto o relativo no supera $10^{-4}$. Formalmente, supongamos que tu salida es $a$ y la respuesta del jurado es $b$; tu salida es aceptada si y solo si $\frac{|a - b|}{\max(1, |b|)} \le 10^{-4}$.
Ejemplos
Entrada 1
1 2 10 1 100
Salida 1
50.5
Entrada 2
3 5 3 4 7 1 2 3 5 8
Salida 2
7.4
Entrada 3
2 4 -1 -2 -3 -4 -5 -6
Salida 3
-1
Entrada 4
5 14 1 3 5 7 9 -1 -1 0 0 2 2 4 4 6 6 8 8 10 10
Salida 4
9.505494505