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

문제

삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리만 닿아 있어야 한다. 삼각형을 뒤집을 순 없다. 완성된 육각형은 다음과 같다.

점수를 계산하는 기준은 육각형의 각 변에 쓰인 숫자들의 합이다.

당신은 어떤 삼각형 세트를 부여받았을때 그 세트에서 나올 수 있는 최고점수를 계산하는 것이다.

입력

입력은 여러개의 세트로 이루어져 있다.

각 세트는 1이상 100이하의 정수 세개로 이루어진 수열 6개로 이루어져 있다.

수열 안의 수는 삼각형 변에 쓰여 있는 수를 시계방향으로 왼쪽부터 입력한 것이다.

세트는 별표(*) 하나를 포함하고 있는 줄로 구분된다.

마지막 세트는 달러($)기호로 종결한다.

출력

각 세트 순서에 맞추어, 육각형 형성이 가능하다면 육각형의 최고점수를, 불가능하다면 none을 출력한다.

예제 입력

1 4 20 
3 1 5 
50 2 3 
5 2 7 
7 5 20 
4 7 50 
* 
10 1 20 
20 2 30 
30 3 40 
40 4 50 
50 5 60 
60 6 10 
* 
10 1 20 
20 2 30 
30 3 40 
40 4 50 
50 5 60 
10 6 60 
$

예제 출력

152 
21 
none

힌트