Problem Description

The people of Paken Island have decided to revise the rules of the school competition because only two students per school can participate, which they consider a problem. (school competition 1)

Among the $ N $ students at anmichi school, the rating of the $ i $th student is $ A_i $, and among the $ M $ students at sanada school, the rating of the $ j $th student is $ B_j $. Here are the rules:

• Both schools divide their students into two teams, A and B. anmichi school's A team competes against sanada school's A team, and anmichi school's B team competes against sanada school's B team.
• For both schools, the total rating of the students in the A team must be strictly greater than the total rating of the students in the B team.
• When two teams compete, the team with the higher total rating wins. If the total ratings are equal, the result is a draw.
• Each team must have at least one student.
• A student cannot be in both the A team and the B team, nor can a student be in neither team.

anmichi school wants to win both the A team and B team matches against sanada school. Calculate the probability that anmichi school can win both teams when they make the best possible team division.

Note that sanada school's team division is chosen equally likely from all valid ways to divide the students that satisfy the above conditions. Two team divisions for sanada school are considered different if there exists a student who is in different teams in the two divisions.

It is guaranteed that there is at least one valid way to divide the teams for both anmichi school and sanada school.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $
$ A_1 $ $ A_2 $ $\ldots$ $ A_{N-1} $ $ A_N $
$ B_1 $ $ B_2 $ $\ldots$ $ B_{M-1} $ $ B_M $

Output Format

Output the probability that anmichi school can win both teams against sanada school when they make the optimal team division. The answer will be considered correct if the absolute or relative error is less than $ 10^{-6} $. Note that a draw does not count as a win.

Sample Input and Output

Sample Input #1

2 23 24 1

Sample Output #1

0.0000000000

Sample Input #2

None

Sample Output #2

1.0000000000

Notes/Hints

Constraints

• All inputs are integers.
• $2\leq\ N,M\ \leq\ 20$
• $0\ \leq\ A_i,B_i\ \leq\ 10^{9}$
• It is guaranteed that there is at least one valid way to divide the teams for both anmichi school and sanada school.

Sample Explanation 1

anmichi school puts the 1st student in the A team and the 2nd student in the B team. sanada school puts the 1st student in the A team and the 2nd student in the B team. In this case, the B team can win, but the A team cannot, so the probability of winning both teams is $ 0 $.

Sample Explanation 2

anmichi school puts the 2nd student in the A team and the 1st student in the B team. There are two ways sanada school can divide their teams:
- The A team consists of the 1st and 3rd students, and the B team consists of the 2nd student.
- The A team consists of the 2nd and 3rd students, and the B team consists of the 1st student.

In both cases, anmichi school can win both teams, so the probability is $ 1 $. Note that in sanada school's division, students with the same rating are distinguished, and team divisions with the same ratings are also distinguished.

见题面 Input 部分

见题面 Output 部分