게임 쇼

코로나19 방역 규정 때문에 여러 장소가 필요한 콘텐츠를 촬영하기 어려워졌다. 그래서 Goosefilm Media는 세 팀이 집안일을 완수해 상금을 받는 게임 쇼를 제작하기로 했다. 그러나 제작이 급하게 진행된 탓에 규칙을 충분히 검토하지 못했다.

이 게임 쇼에서 세 팀은 $3 \times N$개의 집안일을 나누어 수행한다. 각 팀은 집안일마다 성공적으로 완수할 확률이 정해져 있고, 팀들이 서로를 잘 알기 때문에 모든 팀의 모든 확률을 안다. 진행 방식은 다음과 같다. 첫 번째 팀이 전체 $3 \times N$개의 집안일에서 자신들이 수행할 $N$개를 고른다. 그다음 두 번째 팀이 남은 $2 \times N$개에서 $N$개를 고르고, 세 번째 팀은 앞선 두 팀이 고르지 않은 $N$개를 받는다. 이후 세 팀은 카메라가 가득한 저택에서 집안일을 한다. 시간이 끝나면 각 팀은 완수한 집안일 하나마다 $1000를 받고, 여기서 세 팀이 완수한 집안일 수의 평균에 $1000를 곱한 금액을 뺀다. 완수한 집안일 수가 평균보다 적은 팀은 상금이 음수가 되므로, 그 금액을 게임 쇼 제작진에게 지불해야 한다.

1번 팀은 좋은 성적을 내고 싶어 자신들의 기대 상금을 최대화하도록 $N$개의 집안일을 고르기로 했다. 2번 팀은 이 터무니없는 규칙에 불만이 있어, 1번 팀의 기대 상금을 최소화하도록(때로는 1번 팀이 돈을 내게 만들도록) $N$개의 집안일을 고르기로 했다. 3번 팀은 아무것도 고를 수 없지만 맡은 집안일에 최선을 다한다. 이 조건에서 1번 팀의 기대 상금 또는 벌금은 얼마인가? 게임이 시작되기 전에 1번 팀은 2번 팀이 자신들의 선택으로 1번 팀을 방해할 것이라는 사실을 알게 되었고, 이를 고려한다.

첫째 줄에 정수 $N$이 주어진다. $N$은 각 팀이 맡을 집안일 수이며, $1 \le N \le 50\,000$이다. 다음 세 줄에는 각각 $3 \times N$개의 수가 주어진다. 첫째 줄은 1번 팀이, 둘째 줄은 2번 팀이, 셋째 줄은 3번 팀이 각각 $3 \times N$개의 집안일을 완수할 확률이다. 입력으로 주어지는 각 확률은 0 이상 1 이하의 부동소수점 수이다.

1번 팀의 기대 상금을 하나의 수로 출력한다. 출력값이 심사위원의 정답과의 차이가 $10^{-6}$ 미만이면 정답으로 인정된다.

1번 팀이 세 선택지 중 첫 번째 집안일을 완수할 확률이 가장 낮더라도, 최적해에서는 그 집안일을 골라야 한다. 그렇지 않으면 2번 팀이나 3번 팀이 그 집안일을 반드시 완수하기 때문이다.