Un nombre peut être perçu de deux manières.
Si on s'attache au sens du nombre (perception sémantique), alors 1234 représente l'entier de valeur 1234.
Au contraire, si on étudie sa représentation (perception syntaxique), alors 1234 n'est que la concaténation des caractères 1, 2, 3 et 4.
Ainsi, si on étudie la syntaxe d'un nombre donné, on peut en extraire des sous-chaînes représentant d'autres nombres.
Par exemple, 1, 2, 3, 4 12, 23, 34, 123, 234 et 1234 sont les sous-chaînes pouvant être extraites de l'entier 1234.
L'objectif de ce problème est de trouver une partition de l'entrée en sous-chaînes, certaines d'entre elles pouvant représenter des nombres premiers, et telles que la somme des sous-chaînes représentant des nombres premiers est maximale.
On supposera que les nombres premiers ne dépassent pas 10^5.
Par exemple, 1234 peut-être découpé en 1 2 3 et 4, auquel cas seuls 2 et 3 sont premiers et la somme fait 5.
Ou alors 1234 peut être découpé en 1 23 et 4, et la somme fait alors 23.
En fait, dans le cas de 1234, on ne peut pas faire mieux que 23.
L'entrée est constituée d'une unique ligne, contenant le nombre à étudier. Ce nombre ne sera pas plus long que 300 chiffres.
La sortie sera constituée d'une seule ligne, donnant la somme des nombres premiers dans la partition trouvée.
| Entrée | Nombres premiers | Sortie |
|---|---|---|