삼각형 게임

삼각형 게임에서는 시작할 때 삼각형 6개를 받는다. 각 삼각형의 세 변에는 숫자가 하나씩 적혀 있다(위 그림 참고). 이 삼각형들을 회전하거나 위치를 옮겨서 하나의 육각형을 만들어야 한다. 단, 서로 맞닿는 두 변에는 반드시 같은 숫자가 적혀 있어야 하며, 삼각형을 뒤집을 수는 없다(회전만 허용된다). 완성된 육각형의 모습은 다음과 같다.

점수는 완성된 육각형의 바깥쪽 여섯 변에 적힌 숫자들의 합으로 정해진다.

주어진 삼각형 세트로 만들 수 있는 육각형의 최고 점수를 구하여라.

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

각 세트는 6개의 줄로 구성되며, 각 줄에는 삼각형 하나를 나타내는 1 이상 100 이하의 정수 세 개가 주어진다. 세 정수는 삼각형의 세 변에 적힌 수를, 왼쪽 변부터 시작해 시계 방향 순서로 나열한 것이다.

한 세트는 별표(*) 하나만 있는 줄로 다음 세트와 구분되며, 마지막 세트 뒤에는 달러 기호($) 하나만 있는 줄이 온다.

각 세트에 대해 입력 순서대로 한 줄씩 출력한다. 육각형을 만들 수 있으면 가능한 최고 점수를, 만들 수 없으면 none을 출력한다.