속임수 전쟁

Naomi와 Ken은 가끔 함께 게임을 한다. 게임을 시작하기 전에 두 사람은 각각 질량이 0.0kg과 1.0kg 사이인(양 끝값 제외) 겉보기에 똑같은 나무 블록 N개를 받는다. 모든 블록의 무게는 서로 다르다. 이 블록들로 할 수 있는 게임은 많지만, 두 사람은 보통 War라고 부르는 게임을 한다. War의 진행 방식은 다음과 같다.

• 각 플레이어는 자신의 블록을 하나씩 모두 달아 본다. 따라서 각 플레이어는 자신의 모든 블록의 무게를 알지만, 상대 플레이어의 블록 무게는 알지 못한다.

• 두 사람은 다음 과정을 N번 반복한다.

• Naomi는 질량이 Chosen_{Naomi}인 자신의 블록 하나를 선택한다.

• Naomi는 자신이 선택한 블록의 질량을 Ken에게 말한다.

• Ken은 질량이 Chosen_{Ken}인 자신의 블록 하나를 선택한다.

• 두 사람은 각자의 블록을 양팔저울의 한쪽에 각각 올리고, 더 무거운 블록을 낸 사람이 한 점을 얻는다.

• 두 블록은 모두 불에 타서 없어진다.

Naomi는 War에 관해 세 가지를 깨달았다. 첫째, 자신이 아주 많이 진다는 것을 깨달았다. 둘째, Naomi의 전략에 관해 아무것도 가정하지 않고도 Ken이 자신의 점수를 최대화하기 위해 따를 수 있는 유일한 전략이 있으며, Ken은 언제나 그 전략을 사용한다는 것을 깨달았다. 셋째, 자신이 지는 것을 싫어한다는 것을 깨달았다. Naomi는 War 대신 자신이 Deceitful War이라고 부르는 게임을 하기로 했다. Deceitful War의 훌륭한 점은 Ken이 두 사람이 War를 하고 있다고 생각한다는 것이다!

Deceitful War의 진행 방식은 다음과 같으며, Deceitful War과 War의 차이점은 굵게 표시되어 있다.

• 각 플레이어는 자신의 블록을 하나씩 모두 달아 본다. Naomi는 Ken이 보지 않을 때 Ken의 블록도 달아 보므로, Naomi는 모든 블록의 무게를 알고 Ken은 자신의 블록 무게만 안다.

• 두 사람은 다음 과정을 N번 반복한다.

• Naomi는 질량이 Chosen_{Naomi}인 자신의 블록 하나를 선택한다.

• Naomi는 0.0kg과 1.0kg 사이의(양 끝값 제외) 수 Told_{Naomi}을 Ken에게 말한다. 두 사람이 War를 하고 있다고 생각하는 Ken은 Naomi가 방금 말한 수가 Chosen_{Naomi}이라고 생각한다.

• Ken은 질량이 Chosen_{Ken}인 자신의 블록 하나를 선택한다.

• 두 사람은 각자의 블록을 양팔저울의 한쪽에 각각 올리고, 더 무거운 블록을 낸 사람이 한 점을 얻는다.

• 두 블록은 모두 불에 타서 없어진다.

Naomi는 자신이 War를 하고 있지 않다는 사실을 Ken이 알기를 원하지 않는다. 따라서 낼 블록과 Ken에게 말할 질량을 선택할 때, 양팔저울로 인해 Chosen_{Naomi} ≠ Told_{Naomi}라는 사실이 드러나지 않도록 해야 한다. 다시 말해 다음 조건을 만족하도록 결정해야 한다.

• Chosen_{Naomi} > Chosen_{Ken}일 때, 그리고 그럴 때에만 Told_{Naomi} > Chosen_{Ken}이고,

• Told_{Naomi}은 Ken의 어떤 블록의 질량과도 같지 않아야 한다. Ken은 그것이 가능하지 않다는 것을 알기 때문이다.

Ken이 Naomi가 War를 하고 있지 않았다는 사실을 알아챌 수도 있으므로 Naomi가 속임수를 써도 추가로 점수를 얻지 못할 것처럼 보일 수 있다. 하지만 Naomi는 Ken이 두 플레이어 모두 War를 하고 있다고 생각한다는 것을 알고, Ken이 무엇을 아는지도 알며, Ken이 언제나 War에서의 유일한 최적 전략을 따른다는 것도 안다. 따라서 Naomi는 Ken이 무엇을 낼지 언제나 예측할 수 있다.

Naomi와 Ken이 처음에 가진 블록들의 질량이 주어진다. Naomi는 최대한 많은 점수를 얻도록 Deceitful War을 최적으로 플레이한다. Ken은 두 플레이어 모두 War를 하고 있다고 가정하고 최대한 많은 점수를 얻도록 War를 최적으로 플레이한다. Naomi의 점수는 몇 점인가? Naomi가 대신 War를 최적으로 플레이했다면 몇 점이었겠는가?

예제

각 플레이어에게 블록이 하나씩 남아 있고 Naomi의 블록은 0.5kg, Ken의 블록은 0.6kg이라면 Ken이 반드시 그 점수를 얻는다. Naomi는 자신이 말하는 수가 ≥ 0.6kg이라고 말할 수 없다. 그렇게 말했다가 양팔저울에서 Ken의 블록이 더 무거운 것으로 나타나면, Ken은 Naomi가 War를 하고 있지 않다는 사실을 알게 되기 때문이다.

각 플레이어에게 블록이 두 개씩 남아 있고 Naomi에게는 $[0.7kg, 0.2kg]$, Ken에게는 $[0.8kg, 0.3kg]$가 있다면, Naomi는 자신의 0.2kg 블록을 선택하고 자신이 0.6kg인 블록을 선택했다고 Ken에게 말해 그를 속일 수 있다. Ken은 War의 진행 방식대로 Naomi가 진실을 말한다고 가정하고, 점수를 얻기 위해 자신의 0.8kg 블록을 낸다. Ken은 방금 속았지만, 양팔저울에서 자신의 0.8kg 블록이 예상대로 Naomi가 낸 블록보다 더 무거운 것으로 나타나므로 그 사실을 결코 알아차리지 못한다. 이제 Naomi는 자신의 0.7kg 블록을 내고 Ken에게 그 질량이 0.7kg이라고 말하여 한 점을 얻을 수 있다. Naomi가 Deceitful War 대신 War를 했다면 Ken은 두 점을 얻고 Naomi는 영 점을 얻었을 것이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 50. Ken과 Naomi에게 주어진 모든 질량은 서로 다르며, 0.0과 1.0 사이이다(양 끝값 제외).

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각 플레이어가 가진 블록의 수를 나타내는 하나의 정수 N이 담긴 줄로 시작한다. 다음 줄에는 Naomi의 블록 질량을 kg 단위로 나타내는 N개의 실수가 공백으로 구분되어 주어진다. 마지막 줄에는 Ken의 블록 질량을 kg 단위로 나타내는 N개의 실수가 공백으로 구분되어 주어진다.

Ken과 Naomi에게 주어지는 각 질량은 0로 표현되고, 그 뒤에 소수점과 1-5개의 숫자가 이어진다. 입력의 모든 수에는 소수점 뒤에 1-5개의 숫자가 있지만 Ken과 Naomi는 그 사실을 모른다. 따라서 Naomi는 여전히 자신이 질량이 0.5000001kg인 블록을 냈다고 Ken에게 말할 수 있으며, Ken에게는 그 말을 믿지 않을 이유가 없다.

각 테스트 케이스마다 "Case #x: y z"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 Naomi가 Deceitful War을 최적으로 플레이할 때 얻는 점수이며, z는 Naomi가 War를 최적으로 플레이할 때 얻는 점수이다.