랜덤게임

새 학기를 맞아 TCLAB 사람들이 양평으로 엠티를 갔다. 어색한 분위기를 풀려고 다 같이 둘러앉아 게임을 하기로 했는데, 좋아하는 게임이 저마다 달랐다. 그래서 여러 게임을 정해진 확률로 섞어서 하는 랜덤게임을 하기로 했다. 게임을 섞으면 참가자 모두가 평균적으로 어느 정도는 만족하는 구성을 만들 수 있다.

정군과 하군이 엠티에 갔고, 2인용 보드게임 발룬컵, 루미큐브, 로스트시티, 아발론이 준비되어 있다고 하자. 두 사람이 각 게임에 매긴 만족도는 다음과 같다.

여기서 다음 확률분포로 게임을 고르면 두 사람의 평균만족도가 모두 7.5가 된다. 이 예에서는 더 낮은 쪽의 평균만족도를 7.5보다 높게 만드는 확률분포가 없다.

만족도 행렬 $V$를 다음과 같이 정의한다. 참가자의 집합은 $D = \{1, 2\}$, 게임의 집합은 $G = \{1, 2, \dots, n\}$이고, $V_{ij}$는 참가자 $j$가 게임 $i$에 매긴 만족도이다. 게임 $i$가 시행될 확률을 $p_i$라 하면 참가자 $j$의 평균만족도는 $V_j = \sum_{i=1}^{n} V_{ij} p_i$이다. 확률의 정의에 따라 모든 $p_i$는 0 이상이고 $\sum_{i=1}^{n} p_i = 1$이다.

두 참가자의 만족도가 주어질 때, $\min_{1 \le j \le 2} V_j$를 최대로 만드는 확률분포에서의 그 최댓값을 구하시오. 최댓값만 구하면 되고, 그 값을 만드는 확률분포는 출력하지 않는다.

이 문제에서는 참가자가 두 명인 경우만 다룬다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫 줄에는 게임의 개수 $N$ ($1 \le N \le 10^6$)이 주어진다. 둘째 줄에는 참가자 1이 게임 1번부터 $N$번까지에 매긴 만족도가 순서대로 공백을 사이에 두고 주어지고, 셋째 줄에는 참가자 2의 만족도가 같은 순서로 주어진다. 만족도는 모두 0 이상 10000 이하의 정수이다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 최소평균만족도 $\min_{1 \le j \le 2} V_j$의 최댓값을 한 줄에 하나씩 출력한다. 값은 소수점 아래 셋째 자리에서 반올림해 소수점 아래 둘째 자리까지 적는다. 셋째 자리 숫자가 5 이상이면 올리고, 그렇지 않으면 버린다. 답이 정수여도 3.00처럼 소수점 아래 두 자리를 모두 적는다.