Jayce joue une partie d'ARAM: Mayhem. Il a atteint la phase de sélection d'optimisation et cherche l'optimisation parfaite pour porter son équipe. Plus précisément, il chasse désespérément l'optimisation Or connue sous le nom de Slow and Steady.
L'interface du jeu pour la sélection des cartes. Oups, il semble que Jayce ne puisse pas trouver Slow and Steady dans la réserve Prismatique...
Actuellement, l'interface du jeu présente $k$ cartes d'optimisation à Jayce. Bien que chaque carte ait un effet différent, pour Jayce, la $i$-ème carte visible vaut $a_i$ points de valeur. Il y a une réserve cachée de $n$ autres cartes d'optimisation qui attendent dans le paquet. On sait que les points de valeur de ces cartes forment le multiensemble $\{b_1, b_2, \dots, b_n\}$, mais leur ordre est mélangé uniformément au hasard.
Jayce peut actualiser chacun des $k$ emplacements de carte au plus une fois. Le processus fonctionne comme suit :
- Il y a des boutons de relance individuels sous chacune des $k$ cartes (comme illustré dans l'interface du jeu).
- Jayce peut choisir un emplacement qui n'a pas encore été relancé, défausser la carte actuelle et piocher la carte du dessus du paquet pour la remplacer.
- Jayce voit immédiatement le résultat d'une relance avant de décider de son prochain coup : relancer un autre emplacement disponible, ou s'arrêter.
À la fin du processus, Jayce sélectionnera une carte parmi les $k$ cartes actuellement visibles à l'écran.
Jayce joue de manière optimale pour maximiser l'espérance de la valeur de la carte qu'il choisit finalement. Calculez ce niveau de puissance espéré maximal.
Entrée
La première ligne contient deux entiers $k$ et $n$ ($1 \le k \le n \le 10^5$), indiquant le nombre d'emplacements visibles et le nombre de cartes dans le paquet.
La deuxième ligne contient $k$ entiers $a_1, a_2, \dots, a_k$ ($-10^5 \le a_i \le 10^5$), indiquant les niveaux de puissance des cartes initialement visibles.
La troisième ligne contient $n$ entiers $b_1, b_2, \dots, b_n$ ($-10^5 \le b_i \le 10^5$), indiquant les niveaux de puissance des cartes dans le paquet.
Sortie
Affichez l'espérance maximale de la valeur de la carte sous la forme d'un unique nombre réel décimal.
Votre réponse sera considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-4}$. Formellement, en supposant que votre sortie soit $a$ et que la réponse du jury soit $b$, votre sortie est acceptée si et seulement si $\frac{|a - b|}{\max(1, |b|)} \le 10^{-4}$.
Exemples
Entrée 1
1 2 10 1 100
Sortie 1
50.5
Entrée 2
3 5 3 4 7 1 2 3 5 8
Sortie 2
7.4
Entrée 3
2 4 -1 -2 -3 -4 -5 -6
Sortie 3
-1
Entrée 4
5 14 1 3 5 7 9 -1 -1 0 0 2 2 4 4 6 6 8 8 10 10
Sortie 4
9.505494505