You Shall Pass

COT 3100 (Introduction to Discrete Structures) 과목에서 낙제하는 학생이 많아져 UCF 교수들이 크게 우려하고 있다. Matt와 Sean은 방대한 데이터를 모아 분석했고, 몇 가지 확률을 얻었다.

학생마다 기본 확률이 두 개 있다. Matt의 수업에 합격할 확률과 Sean의 수업에 합격할 확률이다. 또한 학생 $i$와 $j$의 쌍마다 값 $a_{ij}$가 주어진다. 학생 $i$와 $j$가 같은 수업에 속하면 스터디 그룹을 만들 수 있고, 그러면 학생 $i$의 합격 확률이 $a_{ij}$만큼 올라간다. 예를 들어 학생 $i$의 초기 합격 확률이 0.4이고 $a_{ij} = 0.2$이면, $j$와 같은 수업에 있을 때 $i$의 합격 확률은 $0.4 + 0.2 = 0.6$이 된다.

Matt와 Sean은 기대 합격 인원이 최대가 되도록 학생들을 두 수업으로 나누려 한다. 모든 학생은 정확히 한 수업에 속하지만, 한 수업이 비어 있을 수도 있다.

초기 합격 확률과 스터디 그룹으로 인한 상승분이 주어졌을 때, 학생들을 두 수업으로 나누는 모든 방법 가운데 얻을 수 있는 기대 합격 인원의 최댓값을 구하라. 어떤 수업 배정에서든 스터디 그룹의 효과를 반영한 후에도 어떤 학생의 합격 확률도 1을 넘거나 0 아래로 내려가지 않는다고 가정한다.

첫 줄에는 확인할 학기 수를 나타내는 양의 정수 $g$가 주어진다. 각 학기의 데이터는 그 학기에 COT 3100을 신청한 학생 수 $n$ ($2 \le n \le 50$)으로 시작한다.

다음 두 줄에는 각각 $n$개의 실수가 주어진다. 첫 번째 줄의 $i$번째 값은 학생 $i$가 Matt의 수업에 합격할 확률이고, 두 번째 줄의 $i$번째 값은 학생 $i$가 Sean의 수업에 합격할 확률이다.

이어서 $n$개의 줄이 주어진다. $i$번째 줄에는 $n$개의 음이 아닌 실수가 있으며, 그 $j$번째 수가 $a_{ij}$이다.

입력의 모든 실수는 소수점 아래 두 자리까지 #.## 형식으로 주어진다.

각 학기마다 기대 합격 인원의 최댓값을 한 줄에 출력한다. 답은 소수점 아래 둘째 자리까지 반올림한다 (예를 들어 1.234는 1.23, 1.235는 1.24가 된다).