Suma de primers P45593

Cal partir un vector amb $n$ nombres naturals en un o més trossos consecutius. Sigui $s_i$ la suma dels nombres del tros $i$-èsim. El valor de cada partició és la suma dels $s_i$ que siguin nombres primers. L’objectiu és maximitzar aquest valor.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, seguida de @V[0]@, …@V[n-1]@. Suposeu $1 \le n \le 1000$, que els nombres donats no són negatius, i que la suma dels nombres de cada cas no passa de $10^7$.

Sortida

Per a cada cas, escriviu el valor de la millor partició possible.

Pista

Precalculeu eficientment abans de començar a llegir l’entrada un vector que indiqui quins nombres són primers i quins no.