Algarvu-Scrabble

Algarvu-Scrabble is a single-player board game. The player receives $N$ tiles, each printed with a single digit from $0$ to $9$. A tile's value is the digit written on it, except that a tile showing $0$ is worth $10$ points.

You build a single row by placing the tiles one at a time. An existing row may be extended at its left end or its right end, but tiles already on the board can never be rearranged.

Each time you place a tile you score if the current row, read left-to-right, is a prime number, and/or read right-to-left, is a prime number. For every direction that reads as a prime you earn the sum of the values of all tiles currently in the row. If both directions are prime at once, you score for both (that is, $2$ times the sum). A number may start with $0$ (for example, 07 reads as $7$). For instance, if the row is 167, then both 167 and 761 are prime, so that placement scores $2 \times (1 + 6 + 7)$.

At the end of the game the row on the board must itself be prime (in at least one direction). If it is impossible to finish on a prime using all of your tiles, you may leave some tiles unplaced; each unplaced tile costs you its value as a penalty, which is subtracted from your score.

Your total score equals (the sum of the points earned on every placement) minus (the sum of the values of the unplaced tiles). Find the maximum total score obtainable with the given tiles.

The first line contains the number of tiles $N$ ($1 \le N \le 8$). The second line contains $N$ space-separated integers (the tiles).

Print a single integer: the maximum total score obtainable. If no non-empty combination of tiles can end on a prime, then no tile can ever score, so every tile becomes a penalty and the answer is the negative of the total value of all tiles.