시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 0 0 0 0.000%

문제

어떤 프로그래밍 대회의 코치는 본인의 팀이 부족한 팀워크 때문에 실망했다. 그래서 그는 잘알려진  비유를 통해 그의 학생들에게 팀워크의 중요성에 대해 시범을 보이기로 결심했다. 한개의 나무 막대는 쉽게 두동강을 낼 수 있다. 하지만 세개를 같이 묶으면(즉, 팀원 셋) 막대를 부서뜨리기 위해서 많은 힘을 가해야 할 것이다. 코치는 그 시범을 통해서라면 그들의 팀원들이 팀워크의 중요성에 대해서 이해할 것이라고 확신했다.

그리하여 코치는 숲으로가 나무 막대를 모았다. 코치는 시범은 항상 리허설이 되어 어떠한 문제도 없어야 한다는것을 알고 있다. 그는 현실적으로 세 개의 막대를 부러뜨리는 것은 불가능하고, 한개씩은 쉽다고 확신했다. 오 이런! 그가 조심히 모은 모든 막대들이 작은 조각들로 부서져 있었다. 그는 다른 막대를 모을 수도 있었지만, 그 막대들로 시범을 보일 수 있다는 것을 어떻게 알았을까? 

코치는 마침내 현명한 아이디어를 내었다. 그냥 더 긴 막대에 조각들을 붙이면 되었다!  막대들은 설사 그들이 다른 막대로부터 나온 조각임에도 불구하고 서로 붙이면 단단히 붙을 것처럼 보였다. 그래서 그는 두개 혹은 그 이상의 막대 조각을 붙여 다시 만들 수 있었다. 새로 만들어진 막대는 하나의 이점을 더하게 되었는데, 접착부분에 있어서는 매우 잘 부러진다는 것이었다. 하지만, 만약 두개의 막대의 이어진 부분이 같은 위치라면, 설사 두개가 같이 있음에도 불구하고 쉽게 부러진다. 그래서 그는 새개의 막대가 접착 부분이 동일하지 않도록 막대를 만들어야만 한다. 더 나아가 새로 만들어지는 막대는 가능한한 길게 만들고 싶다. 최종적으로 세 개의 막대는 그 길이가 같아야만 한다. - 코치는 한 팀원이 다른 팀원보다 더 우월하다는 것을 내포 하고 싶지 않기 때문이다. 조각들을 사용하지 않고 남기는 것은 허용된다. 물론 각 조각들은 한번만 사용되어야 한다.

입력

입력은 여러 케이스로 구성이 되어있다. 각 케이스는 한 줄에 명시된다. 첫번째 숫자는 (N) 조각의 갯수를 의미한다. 이후에 따라오는 N개의 숫자는 각 조각의 길이를 명시하는 양의 정수이다. 최대 13개까지의 조각이 올 수 있다.  0을 입력하였을 경우 입력이 종료된다.

출력

각 케이스 별로, 케이스의 번호가 콜론(:)앞에 오고, 가능한 가장 긴 길이의 새로 만들어진 막대가 한줄에 표시된다. 만약 주어진 조건으로 불가능하다면, 0을 가장 긴 막대의 길이로 출력하면된다. 

예제 입력

10 4 2 3 7 8 9 1 2 3 4
10 1 2 3 4 5 6 7 8 9 10
8 2 3 4 1 1 3 2 2
10 25 25 25 25 25 25 25 25 25 25
0

예제 출력

Case 1: 14
Case 2: 18
Case 3: 6
Case 4: 0

힌트