소수 스크래블

소수 스크래블은 혼자서 즐기는 타일 게임입니다. 당신은 타일 $N$개를 받으며, 각 타일에는 $1$부터 $9$까지의 숫자가 하나씩 적혀 있습니다. 타일의 값은 거기에 적힌 숫자와 같습니다.

타일을 나란히 놓아 하나의 가로줄을 만듭니다. 처음에는 타일 하나로 줄을 시작하고, 그 뒤로 타일을 놓을 때마다 현재 줄의 왼쪽 끝 또는 오른쪽 끝에 타일 하나를 덧붙여 줄을 늘립니다. 이미 놓인 타일의 위치는 절대 바꿀 수 없습니다.

현재 판에 놓인 줄을 왼쪽에서 오른쪽으로 읽었을 때 소수가 되면, 그 순간 판에 놓인 모든 타일의 값의 합만큼 점수를 얻습니다. 오른쪽에서 왼쪽으로 읽어도 소수라면 같은 점수를 한 번 더 얻습니다. 따라서 어떤 줄이 양쪽 방향 모두에서 소수이면 그 줄을 완성한 순간에 타일 값 합의 두 배를, 한쪽 방향에서만 소수이면 한 배를 얻습니다. (한 자리 소수나 앞뒤로 대칭인 소수는 두 방향 모두에서 소수로 읽히므로 두 배의 점수를 얻습니다.)

마지막으로 타일을 놓은 뒤의 최종 줄은 적어도 한 방향에서 소수로 읽혀야 합니다. 판에 놓지 않고 손에 남긴 타일은 각각 그 값만큼 점수를 깎는 벌점이 됩니다. 어떤 소수도 만들 수 없다면 아무 타일도 놓지 않고 모든 타일을 벌점으로 남길 수 있습니다.

소수란 $1$보다 큰 정수 중 약수가 $1$과 자기 자신뿐인 수입니다. 예를 들어 $2, 3, 5, 7$은 소수이지만, $4$는 $2$로 나누어지고 $6$은 $2$와 $3$으로 나누어지므로 소수가 아닙니다.

총점은 각 차례에 얻은 점수의 합에서 손에 남은 타일들의 값의 합을 뺀 값입니다. 얻을 수 있는 최대 총점을 구하세요.

첫 번째 줄에 타일의 개수 $N$ ($1 \le N \le 8$)이 주어집니다. 두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, 각 정수는 $1$ 이상 $9$ 이하입니다(타일에 적힌 숫자).

얻을 수 있는 최대 총점을 정수 하나로 출력합니다. 이 값은 소수를 만들어 얻은 점수의 합에서 손에 남은 타일들의 값의 합을 뺀 것이며, 음수가 될 수 있습니다.