You Shall Pass

Students who fail COT 3100 (Introduction to Discrete Structures) have become a major concern for the UCF professors. Matt and Sean collected a large amount of data and analyzed it, and they produced some probability estimates.

Each student has two base probabilities: the probability of passing Matt's class and the probability of passing Sean's class. Each pair of students $i$ and $j$ also has a value $a_{ij}$. If students $i$ and $j$ are in the same class, they can form a study group, and then student $i$'s probability of passing increases by $a_{ij}$. For example, if student $i$'s initial probability is 0.4 and $a_{ij} = 0.2$, then $i$'s probability of passing with $j$ in the same class becomes $0.4 + 0.2 = 0.6$.

Matt and Sean want to split the students into two classes so that the expected number of students who pass is as large as possible. Every student is in exactly one class, but one class may be empty.

Given the initial passing probabilities and the increases from study groups, find the maximum expected number of passing students over all ways to split the students into two classes. For any class split, assume that no student's passing probability is ever higher than 1 or lower than 0, even after study group effects are counted.

The first line contains a positive integer $g$, the number of semesters to check. The data for each semester starts with an integer $n$ ($2 \le n \le 50$), the number of students who signed up for COT 3100 that semester.

The next two lines each contain $n$ decimal values. The $i$-th value of the first line is the probability that student $i$ passes Matt's class. The $i$-th value of the second line is the probability that student $i$ passes Sean's class.

Then $n$ lines follow. The $i$-th line contains $n$ non-negative decimal numbers, and the $j$-th number on that line is $a_{ij}$.

Every decimal value in the input is written with exactly two decimal places, in the form #.##.

For each semester, print the maximum expected number of passing students on its own line. Round the answer to two decimal places (for example, 1.234 rounds to 1.23 and 1.235 rounds to 1.24).