Prime Scrabble

Prime Scrabble is a single-player tile game. You are given $N$ tiles, each showing a single digit from $1$ to $9$. The value of a tile equals the digit written on it.

You build one horizontal row of tiles. You start the row with a single tile, and on every later placement you extend the current row by adding one tile at its left end or its right end. Tiles already on the board are never rearranged.

Whenever the row currently on the board reads as a prime number from left to right, you immediately score points equal to the sum of the values of all tiles on the board. If it also reads as a prime number from right to left, you score that same amount once more. So a row that is prime in both reading directions scores twice the sum of its tiles at the moment it is completed, while a row that is prime in exactly one direction scores it once. (A single-digit prime, or any palindromic prime, reads as a prime in both directions and therefore scores twice.)

After your final placement, the resulting row must read as a prime in at least one direction. Every tile you never place stays in your hand, and each such tile subtracts its value from your score as a penalty. If no prime can be formed at all, you may place nothing and leave every tile in your hand.

A prime is an integer greater than $1$ whose only divisors are $1$ and itself. For example $2, 3, 5, 7$ are primes, whereas $4$ is divisible by $2$ and $6$ is divisible by both $2$ and $3$, so they are not.

Your total score is the sum of the points earned on your placements minus the total value of the tiles left in your hand. Find the maximum total score you can achieve.

The first line contains the number of tiles $N$ ($1 \le N \le 8$). The second line contains $N$ space-separated integers, each between $1$ and $9$ (the digits on the tiles).

Output a single integer: the maximum total score you can achieve. It equals the points earned from forming primes minus the total value of the tiles left in your hand, and it may be negative.