Algarvu-Scrabble

Algarvu-Scrabble는 혼자서 하는 보드 게임입니다. 플레이어는 각각 $0$부터 $9$까지의 숫자가 하나씩 적힌 게임 조각 $N$개를 받습니다. 각 조각의 값은 적힌 숫자와 같지만, 예외로 숫자 $0$이 적힌 조각의 값은 $10$점입니다.

조각은 한 번에 하나씩 한 줄로 나란히 놓습니다. 이미 시작된 줄은 왼쪽 끝이나 오른쪽 끝으로 늘릴 수 있지만, 이미 놓인 조각의 위치를 바꿀 수는 없습니다.

조각을 하나 놓을 때마다, 현재 줄을 왼쪽에서 오른쪽으로 읽은 수가 소수이거나 오른쪽에서 왼쪽으로 읽은 수가 소수이면 점수를 얻습니다. 소수가 되는 방향 하나마다 현재 줄에 놓인 모든 조각의 값의 합만큼 점수를 얻습니다. 양쪽 방향이 동시에 소수이면 두 방향 모두에 대해 점수를 얻습니다(즉, 합의 $2$배). 수는 $0$으로 시작해도 됩니다(예를 들어 07은 $7$로 읽습니다). 예를 들어 줄이 167이면 167과 761이 모두 소수이므로 이 배치는 $2 \times (1 + 6 + 7)$점을 얻습니다.

게임이 끝났을 때 줄에 놓인 수는 (적어도 한 방향으로) 소수여야 합니다. 모든 조각을 사용해 소수로 끝내는 것이 불가능하면 일부 조각을 놓지 않고 남길 수 있으며, 남긴 각 조각은 그 값만큼 벌점이 되어 점수에서 빠집니다.

총점은 (각 배치에서 얻은 점수의 합)에서 (놓지 않은 조각들의 값의 합)을 뺀 값입니다. 주어진 조각들로 얻을 수 있는 최대 총점을 구하세요.

첫째 줄에 조각의 개수 $N$ ($1 \le N \le 8$)이 주어집니다. 둘째 줄에 공백으로 구분된 $N$개의 정수(게임 조각)가 주어집니다.

얻을 수 있는 최대 총점을 정수 하나로 출력합니다. 비어 있지 않은 어떤 조각 조합으로도 소수로 끝낼 수 없다면 어떤 조각도 점수를 낼 수 없으므로, 모든 조각이 벌점이 되어 답은 모든 조각의 값의 합에 음수를 붙인 값이 됩니다.